Главная

Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Решение систем линейных алгебраических уравнений методом итераций


 

Рассмотрим систему линейных алгебраических уравнений (2.9)

. (2.9)

Если все диагональные элементы (i=1,2,…,n), то систему (2.1) можно представить в приведенном виде (2.10):

, (2.10)

где (i=1,2,…,n)

.

 

Введем обозначения

.

Тогда систему (2.2) можно представить так:

. (2.11)

 

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

– первое приближение;

– второе приближение; (2.12)

. . . . . . . . . . . . .

– (k+1)-е приближение.

Если существует предел x последовательности векторов то, переходя к пределу в равенстве при , убеждаемся, что x является решением уравнения (2.11):

.

Достаточное условие сходимости итерационного процесса представлено ниже.

Теорема. Если какая-нибудь норма матрицы А меньше единицы: , то уравнение (2.11) имеет единственное решение x, к которому стремится последовательность итераций (2.12) при любом выборе начального приближения.

Под нормойматрицы понимают следующие выражения:

 

– (m-норма) сумма модулей элементов строки;

– (l-норма) сумма модулей элементов столбца;

– (k-норма).

Например, для матрицы .

В расчетах полагают . Погрешности приближенного решения уравнения (2.11) на k-м шаге оценивают неравенством

, (2.13)

где – норма вектора X.

– m-норма или кубическая норма;

– l-норма или октаэдрическая норма.

Введем обозначения

.

Тогда система (2.2) запишется в виде

. (2.14)

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

– (k+1)-е приближение. (2.15)

Если существует предел x последовательности векторов то, переходя к пределу в равенстве при , убеждаемся, что x является решением уравнения (2.14):

Достаточное условие сходимости итерационного процесса:

Теорема. Если какая-нибудь норма матрицы А меньше единицы: ( ), то уравнение (2.14) имеет единственное решение x, к которому стремится последовательность итераций (2.15) при любом выборе начального приближения.

Блок-схема решения системы линейных алгебраических уравнений методом Гаусса с выбором главного элемента (по столбцу) приведена на рис. 2.1а, 2.1б.

 

 

Рис.2.1 а

 

C
B
A


Вывод на экран треугольной матрицы   КОНЕЦ ПРЯМОГО ХОДА
Рис. 2.1 б

 

Под нормойматрицы понимают следующие выражения:

– (m-норма) сумма модулей элементов строки;

– (l-норма) сумма модулей элементов столбца;

– (k-норма).

Например, для матрицы .

.

.

.

В расчетах полагают . Погрешности приближенного решения уравнения (2.14) на k-м шаге оценивают неравенством

, (2.16)

где – норма вектора X.

– m-норма, кубическая норма;

– l-норма или октаэдрическая норма;

– k-норма или сферическая норма.

Из неравенства (2.16) можно получить оценку числа итераций k, необходимых для обеспечения заданной точности e.

Отклонение приближения от решения x по норме не будет превышать e, если

. (2.17)

Для вывода (2.17) достаточно рассмотреть равенства:

 

; ; ;

;

; и т.д.

.

Далее .

Учитывая, что , так как норма .

В неравенствах (2.16) и (2.17) используются согласованные нормы для матриц и векторов, то есть m и l-нормы.

Неравенство (2.17) дает завышенную оценку числа итераций k. Из формулы (2.17) можно получить удобное условие, позволяющее принять приближение в качестве решения с точностью e:

. (2.18)Пример:Найти решение системы уравнений

методом итераций с точностью 10-2.

Решение:Приведем систему к виду (2.10)

 

.

Запишем последовательность итераций

 

. (2.19)

Для приведенной матрицы достаточное условие ходимости выполняется по m-норме:

 

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

Число итераций для достижения заданной точности определяем из неравенства (2.13) , которое запишем так:

, действительно:

.

; , так как

 

то ; .

 

Вычислим теперь три последовательных приближения по формулам (2.19) и оценим погрешность каждого результата, используя неравенство (2.18) в виде:

. .

Первое приближение:

 

.

.

Следовательно, дает значение корня ξ с погрешностью, не превышающей величины .

 

Далее последовательно находим:

 

;

.

 

Третья итерация:

 

;

 

.

Заданная точность достигается за пять шагов. Точное решение .

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

 
 


 

Рис. 2.2 а


 

                   
   
 
 
   
     
 
 
   
Рис 2.2 б

 

 


Блок-схема алгоритма решения системы линейных уравнений алгебраических уравнений приведена на рис. 2.2 а, рис. 2.2 б.

 




Последнее изменение этой страницы: 2016-06-10

headinsider.info. Все права принадлежат авторам данных материалов.