Знаходження коренів систем лінійних рівнянь методом Гаусса, методом Зейделя та методом простих ітерацій

Методы последовательных приближений, в которых при вычислении последующего приближения решения используются предыдущие, уже известные приближенные решения, называются итерационными.

Рассмотрим СЛАУ

                                                                                    (1.1)

с невырожденной матрицей .

              Приведем СЛАУ к эквивалентному виду

                                                                                    (1.2)

или в векторно-матричной форме

.                                                                                                               

Такое приведение может быть выполнено различными способами. Одним из наиболее распространенных является следующий.

Разрешим систему (1.1) относительно неизвестных при ненулевых диагональных элементах , (если какой-либо коэффициент на главной диагонали равен нулю, достаточно соответствующее уравнение поменять местами с любым другим уравнением). Получим следующие выражения для компонентов вектора и матрицы эквивалентной системы:

        , .                                          (1.3)

При таком способе приведения исходной СЛАУ к эквивалентному виду метод простых итераций носит название метода Якоби.

В качестве нулевого приближения вектора неизвестных примем вектор правых частей или . Тогда метод простых итераций примет вид:

                                                                                                                (1.4)

Из (1.4) видно преимущество итерационных методов по сравнению, например, с рассмотренным выше методом Гаусса. В вычислительном процессе участвуют только произведения матрицы на вектор, что позволяет работать только с ненулевыми элементами матрицы, значительно упрощая процесс хранения и обработки матриц.

Имеет место следующее достаточное условие сходимости метода простых итераций.

Метод простых итераций (1.4) сходится к единственному решению СЛАУ (1.2) (а следовательно и к решению исходной СЛАУ (1.1)) при любом начальном приближении , если какая-либо норма матрицы эквивалентной системы меньше единицы   

Если используется метод Якоби (выражения (1. 3) для эквивалентной СЛАУ), то достаточным условием сходимости является  диагональное преобладание матрицы , т.е.   (для каждой строки матрицы модули элементов, стоящих на главной диагонали, больше суммы модулей недиагональных элементов). Очевидно, что в этом случае  меньше единицы и, следовательно, итерационный процесс (1.4) сходится.

Приведем также необходимое и достаточное условие сходимости метода простых итераций. Для сходимости итерационного процесса (1.4) необходимо и достаточно, чтобы спектр матрицы эквивалентной системы лежал внутри круга с радиусом, равным единице.

При выполнении достаточного условия сходимости оценка погрешности решения на - ой итерации дается выражением:

,                                                                      (1.5)

где - точное решение СЛАУ.

Процесс итераций останавливается при выполнении условия , где - задаваемая вычислителем точность.

Принимая во внимание, что из (1.5) следует  неравенство , можно получить априорную оценку необходимого для достижения заданной точности числа итераций. При использовании в качестве начального приближения вектора такая оценка определится неравенством:

,

откуда получаем априорную оценку числа итераций при

.

Следует подчеркнуть, что это неравенство дает завышенное число итераций k, поэтому редко используется  на практике.

Замечание. Поскольку является только достаточным (не необходимым) условием сходимости метода простых итераций, то итерационный процесс может сходиться и в случае, если оно не выполнено. Тогда критерием окончания итераций может служить неравенство  .

Пример. Методом простых итераций с точностью решить СЛАУ.

Р е ш е н и е.

Приведем СЛАУ к эквивалентному виду:

или

где ;     ;   

, следовательно достаточное условие сходимости метода простых итераций выполнено.

Итерационный процесс выглядит следующим образом.

;     ; ;

;

;

; .

Рис.2. Решение методом простых итераций.

Вывод.

Таким образом, вычислительный процесс завершен за 4 итерации. Отметим, что точное решение исходной СЛАУ в данном случае известно . Отсюда следует, что заданной точности удовлетворяло решение, полученное уже на третьей итерации. Но в силу использования для вычисления погрешности оценочного выражения (1.5) (видно, что в данном случае , при этом  , хотя   ) процесс останавливается только на четвертой итерации.

Отметим также, что априорная оценка необходимого количества итераций в данной задаче дает: , т.е. для достижения точности , согласно априорной оценке, необходимо сделать не менее пяти итераций, что  иллюстрирует характерную для априорной оценки тенденцию к завышению числа итераций.

2.4 Метод Зейделя.

Метод простых итераций довольно медленно сходится. Для его ускорения существует метод Зейделя, заключающийся в том, что при вычислении компонента   вектора неизвестных на (k+1)-й итерации используются, уже вычисленные на (k+1)-й итерации. Значения остальных компонент берутся из предыдущей итерации. Так же как и в методе простых итераций строится эквивалентная СЛАУ (1.2 и за начальное приближение принимается вектор правых частей . Тогда метод Зейделя для известного вектора на k-ой итерации имеет вид:

.

Из этой системы видно, что , где В - нижняя треугольная матрица с диагональными элементами , равными нулю, а С - верхняя треугольная матрица  с диагональными элементами, отличными от нуля, . Следовательно

откуда

Таким образом, метод Зейделя является методом простых итераций с матрицей правых частей и вектором правых частей и, следовательно, сходимость и погрешность метода Зейделя  можно исследовать с помощью формул, выведенных для метода простых итераций,  в которых вместо матрицы   подставлена матрица , а вместо вектора правых частей – вектор . Для практических вычислений важно, что в качестве достаточных условий сходимости метода Зейделя могут быть использованы условия, приведенные выше для метода простых итераций ( или, если используется эквивалентная СЛАУ в форме (1.3 – диагональное преобладание матрицы ).  В случае выполнения этих условий для оценки погрешности на -ой итерации можно использовать выражение

.

Отметим, что как и метод простых итераций, метод Зейделя может сходиться и при нарушении условия  . В этом случае .

Р е ш е н и е.

Приведение СЛАУ к эквивалентному виду аналогично примеру (1.2). Диагональное преобладание элементов исходной матрицы СЛАУ гарантирует сходимость метода Зейделя.

Итерационный процесс выглядит следующим образом:

Рис.3. Решение методом Зейделя.

Вывод.

Таким образом, уже на второй итерации погрешность , т.е. метод Зейделя в данном случае сходится быстрее метода простых итераций.

ВЫВОД

Огромное количество численных методов ставит актуальной задачей не столько создание новых, сколько исследование и классификацию старых, выявление лучших. Анализ влияния ошибок показал, что между лучшими методами нет принципиальной разницы с точки зрения устойчивости к ошибкам округления. Создание мощных компьютеров существенно ослабило значение различия между методами (в таких характеристиках, как объём требуемой памяти, количество арифметических операций). В этих условия наиболее предпочтительными становятся те методы, которые не очень отличаются от лучших по скорости и удобству реализации на компьютерах, позволяют решать широкий класс задач как хорошо, так и плохо обусловленных и давать при этом оценку точности вычислительного решения.

Программа на Visual С++ намного упрощает задачу. С помощью единожды созданной программы можно решать системы линейных уравнений, вводя минимум  значений.

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1.      Е.П.Путятiн, В.П.Степанов, В.П.Пчелiнов, Т.Г.Долженкова, О.О.Матат. Основи програмування мовою С++: Навчальний посiбник – Х.: ТОВ  «Компанiя Смiт», 2005. – 320 с.

2.      Методичнi вказiвки до курсового проектування з дисциплiни «Програмування» / Упоряд.: Т.Г.Долженкова, Д.О.Руденко – Х.: ХНУРЕ, 2004. – 16 с.

3.      В.П. Дьяконов. Справочник по алгоритмам и программам на языке бейсик для персональных ЭВМ. “Наука” – Москва, 1987. – 240 с.

ПРИЛОЖЕНИЕ А Текст программы

Main.cpp

#include "stdafx.h"

#include "Gauss.h"

#include "Zeidel.h"

#include "SI.h"

#include <conio.h>

using namespace GAUSS;

using namespace ZEIDEL;

using namespace SimpIter;

void main ()

{

              setlocale (LC_ALL, "Rus");

              cout << "********************| Методы решения СЛАУ |*********************\n";

              int Method=9;

              while (Method != 0)

              {

                            cout << "\n*****************************************";

                            cout << "\nВыбирите метод:";

                            cout << "\nМетод Гаусса - нажмите 1";

                            cout << "\nМетод Зейделя - нажмите 2";

                            cout << "\nМетод простых итераций - нажмите 3";

                            cout << "\nВыход - нажмите 0\n";

                            cin >> Method;

                            if (Method==1) Gauss();

                            if (Method==2) Zeidel();

                            if (Method==3) SI ();

              }

}

Gauss.h

#include "stdafx.h"

#include <iostream>

#include <conio.h>

using namespace std;

namespace GAUSS

{

              double **Create (int a, int b)

                            {

                                          double **p = new double *[a];

                                          for (int i=0; i<a; i++)

                                                        p[i] = new double [b];

                                          return p;

                            }

              //============ заполнение ============================================

              void Fill (double **arr, int a, int b)

              {

                            setlocale (LC_ALL, "Russian_Russia.1251");

                            cout << "Введите коэффициенты:\n";

                            for(int i = 0; i < a; i++) {

                                          for(int j = 0; j < b; j++)

                                                        cin >> arr[i][j];

                            }

                            cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n";

              }

              //===================== вывод матрицы ========================================

              void PrintMatr(double **matr, int n, int m)

              {

                            for(int i = 0; i < n; i++) {

                                          cout << "\n";

                                          for(int j = 0; j < m; j++)

                                                        cout << matr[i][j] <<"\t";

                                          cout << "\n";

                            }

                            cout << "\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n";

              }

              //==================== треугольный вид =======================================

              void Change(double **matr, double *mas, const int n)

              {

                            int i,j,k;

                            double t;

                            for(i=0; i<n-1; i++)

                                          for(j=i+1; j<n; j++)

                                                        for(k=n; k>i-1; k--)

                                                                      matr[j][k] = matr[j][k]-matr[i][k]*matr[j][i]/matr[i][i];

                              for(i=n-1; i>=0; i--)

                              {

                                          for(t=0, j=i+1; j<=n-1; j++)

                                                        t = t + matr[i][j]*mas[j];

                                          mas[i] = (matr[i][n] - t)/matr[i][i];

                              }

              }

              // ==================== вывод корней системы =======================

              void PrintResult(double *mas, const int n)

              {

                            cout << "корни системы: " << endl;

                            int i;

                            for(i=0; i<n; i++) {

                                          cout << "\n\tx" <<i+1 <<" = " << mas[i];

                            }

                            cout << "\n\n=============================================\n";

                            cout << "=============================================\n\n";

              }

              void Gauss ()

              {

                            setlocale (LC_ALL, "Russian_Russia.1251");

                            cout << "\n\t\tМЕТОД ГАУССА\n\n";

                            int n, m;

              //====================== ввод кол-ва уравнений =========================

                            bool STOP;

                            do {

                                          cout << "Введите количество уравнений: ";