Итерационные методы
учебно-методический материал по математике

СОДЕРЖАНИЕ

ВВЕДЕНИЕ         3

1 Исходные понятия итерационных методов и область их применения        5

1.1 Понятие итерационных методов        5

1.2 Метод простой итерации        7

1.3 Итерационное уточнение        12

1.4 Метод Зейделя        15

1.5 Метод верхней релаксации        16

2. Решение системы линейных уравнений методом Якоби        19

2.1 Условие сходимости итерационного процесса        19

2.2 Пример решения системы линейных уравнений методом Якоби        20

ЗАКЛЮЧЕНИЕ        22

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ        23

ВВЕДНИЕ

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

Примером обычных итерационных методов служат: метод итераций (метод Якоби), метод Зейделя, метод верхних релаксаций

Цели: определение и изучение понятия итерационные методы; применить к конкретной задачи итерационный метод решения системы линейных уравнений.

Задачи:

1. изучить теоретический материал по данной теме,
2. изучение определений и теорем в соответствии с различными научными подходами,
3. описать основные итерационные методы решения систем линейных уравнений,
4. применить один из итерационных методов решения систем линейных уравнений на практике.

В первой главе описываются определение итерационных методов решения систем линейных уравнений и область их применения. Рассматриваются отдельно методы Якоби, Зейделя и верхней релаксации.

Во второй главе рассматривается пример решения системы линейных уравнений методом Якоби.

1 Исходные понятия итерационных методов и область их применения

1. Понятие итерационных методов

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

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

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

Главным недостатком этих методов является то, что вопрос сходимости итерационного процесса требует отдельного исследования.

Типичная область применения итерационных методов – это системы линейных уравнений, возникающие при численном решении уравнений с частными производными. Обычно это системы из большого числа уравнений с большим число неизвестных, матрицы которых могут легко записываться и обрабатываться только благодаря их специальному строению. Но специальное строение матриц, как правило, нарушается при тез преобразованиях, которым они подвергаются при применении прямых методов. Итерационные методы свободны от этого недостатка.

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

Пусть L – полное линейное нормированное пространство и F –его отображение (не обязательно линейное) в себя. F называется сжимающим множество M ⊆ L, если существует такое число α ∈ [0, 1), что для любых x’ b x’’ из М выполнено условие:

||F(x’) – F(x’’)|| ≤ α ||x’ – x’’||.

Заметим, что определение это применимо и тогда, когда F определено не на всем пространстве L, а только на множестве M.

Теорема 1. Пусть М – замкнутое ограниченное множество в L и отображение F сжимает M. Тогда уравнение

x=F(x) (1)

имеет в M одно и только одно решение.

Доказательство основано на том, что в условиях теоремы любая последовательность вектором {xk} из М, задаваемая рекуррентной формулой

Xk+1= F(xk), (2),

Сходится к решению уравнения (1).

1.2 Метод простой итерации.

Проще всего придать системе линейных уравнений Ах=b вид (1), прибавив x  к обеим частям равенства:

X = x - Аx+b=(E-A)x+b.

Более общую формулу мы получим, если предварительно умножим обе части равенства на невырожденную матрицу H

X=x+H(b-Ax).

Это позволяет построить итерационный процесс, задаваемый рекуррентной формулой

xk+1=xk+xk+H(b-Axk). (3)

Введя параметр τB-1, мы можем переписать формулу (3) в виде

. (4)

Нахождение приближенного решения с использованием формулы (3) называется методом простой итерации или стационарным методом. Формула (4) соответствует общему неявному методу простой итерации. Значение параметра τ выбирается для конкретной системы так, чтобы скорость сходимости была максимальной.

Формулам (3) и (4) можно придать вид

xk+1=Pxk+f, (5)

Если положить P=E-HA, а f=Hb, или соответственно P=E- τB-1A и f= τB-1b.

Допустим, что система Аx=b совместна и x* - ее решение. Вычтем x* из обеих частей равенства (5). Учитывая, что f=Hb=HAx*, мы получим

xk+1-x*=P(xk – x*).

Отсюда, обозначив dk=xk – x* для всех k=0, 1, …, имеем

dk=Pkd0

Нетрудно доказать, что последовательность {dk} сходится при любом d0 (а значит, и {xk} при любом x0) тогда и только тогда, когда сходится последовательность степеней матрицы P. В самом деле, если Pk→Q, то для любого ε’>0 найдется номер k0, начиная с которого ||Pk – Qd0|| ≤ ε’, а следовательно, при любом d0

||dk – Qd0|| ≤ ||Pk – Q|| ||d0|| < ε’||d0||.

Остается при произвольном ε > 0 выбрать ε’= ε|| d0 ||-1.

Обратно, если последовательность Pkd0 сходится при любом d0, то, выбирая в качестве d0 столбцы единичной матрицы, мы покажем, что при всех i=1, …, n сходятся последвательности {}, где  - i-й столбец матрицы Pk. Следовательно, последовательность степеней сходится в смысле поэлементной сходимости.

Мы видели, что dk→Q d0, где Q=Pk, и, следовательно, предел x последовательности {xk} удовлетворяет соотношению

x -x*=Qd0.

С другой стороны, очевидно, что x – решение системы, и потому Qd0 удовлетворяет приведенной однородной системе, т.е. AQd0=0. Это условие выполнено при любом d0, если

AQ=O,

и только в этом случае. Теперь мы можем доказать

Предположение 1. Пусть матрица А системы линейных уравнений Ах=b невырождена. Тогда последовательность столбцов, задаваемая рекуррентной формулой (5), сходится при любому начальном векторе x0 тогда и только тогда, когда спектральный радиус матрицы P меньше единицы.

Доказательство. Вышеуказанные рассуждения показывают, что при невырожденной матрице А последовательность {xk} сходится при любом x0 тогда и только тогда, когда Q=O. Нам остается доказать, что Pk → O тогда и только тогда, когда спектральный радиус P меньше единицы

Где Zij – компонентные матрицы для матрицы P, число различных характеристических числе обозначено через s, а кратность i-о числа – через mi. Отсюда в силу линейной независимости компонентных матриц непосредственно вытекает доказываемое.

Предложение 2. Если ||P|| < 1, то рекуррентная последовательность, задаваемая формулой (5), при любом начальном векторе сходится не медленнее, чем сумма геометрической прогрессии со знаменателем ||P||.

То, что условие ||P||<1 достаточно для сходимости рассматриваемой последовательности, непосредственно вытекает из предложения 1, если вспомнить оценку для спектрального радиуса матрицы. Приведем другое доказательство, позволяющее оценить скорость сходимости. Если для любого k обозначить dk= xk - xk-1, то, как легко видеть, xk=x0+d1+ … +dk.

Следовательно,

x=xk=x0+

Пусть в Rn выбрана некоторая норма, и матричная норма согласована с ней. Используя критерий Коши (см. Кудрявцев, т1,п.18), нетрудно доказать, что для сходимости ряда достаточно сходимости ряда из норм его членов. Для dk имеем dk=P dk-1, откуда ||dk|| ≤ ||P|| *  ||dk-1||, и в случае ||P|| < 1 для ряда из норма выполнен признак Даламбера. Итак, в этом случае последовательность xk сходится не медленнее, чем сумма геометрической прогрессии со знаменателем ||Р||. Предложение доказано.

Выше было сказано о спектральном радиусе матрицы, как о чем-то точно определенном. В действительности, если арифметические операции производятся с округлением, спектральный радиус, как и многие другие величины, не может быть точно указан. В самом деле, пусть существует число λ такое, что матрица P - λE является почти вырожденной. Число λ во всех вычислениях ведет себя так же, как характеристическое число. В частности, если λ>1, то метод простой итерации с матрицей Р не сходится с должной точностью.

В любом случае для ускорения сходимости процесс должен быть построен так, чтобы норма матрицы Р была возможно меньше. Если вернуться к формулам (3) (4), то это означает, что нужно выбрать матрицу Н или соответственно парпаметр τ и матрицу В так, чтобы ||E – HA|| или                 ||E – B-1τА|| были возможно меньше.

Метод Якоби.

Существует сиcтема A·x = f (1), где матрица A = [aij] (i, j = 1, 2, …m) имеет обратную матрицу; x = (x1, x2, x3,… xm) – вектор неизвестных, f – вектор свободных членов. Систему (1) нужно преобразовать к следующему виду:  (2) i=1, 2,…, m, где , , при этом aii 0.

Значение суммы считается равным 0, если верхний предел суммирования меньше нижнего. Тогда при i=1 уравнение имеет вид: (3). В методе Якоби исходят из записи системы в виде (2), итерации при этом определяют следующим образом: , (n=0, 1, …, n0, i=1, 2, …, m) (4).

Начальные значения – (i=0, 1, …, m) задаются произвольно. Окончание итерационного процесса определяют либо заданием максимального числа итераций n0, либо следующим условием: , где >0. В качестве нулевого приближения в системе (4) примем .

Если последовательность приближений x1(0), x2(0),…, xm(0), x1(1), x2(1),…, xm(1),…, x1(k), x2(k),…, xm(k) имеет предел , , то этот предел является решением системы (2).

Достаточным условием сходимости решения системы (1) является то, что матрица A является матрицей с преобладающими диагональными элементами, то есть , i=1, 2, …, m.

1.3 Итерационное уточнение.

Допустим, что, применяя метод гаусса, мы получили LU – разложение матрицы А. Ошибки округления исказили результат, и потому LU≠F для вычисленных матриц L  и U. В общем неявном методе простой итерации мы можем положить B=LU и τ=1. Формула (4) примет вид

LU dk+1=rk, (6)

Где rk = b - Аxk называется k-й невязкой, а dk+1=xk+1 - xk’ – (k+1)-й поправкой. В качестве начального приближения берется решение системы LUx0=b, затем вычисляется соответствующая невязка r0. Она принимается за столбец свободных членов системы с той же матрицей LU. Решение этой системы – первая поправка d1. Следующее приближение x1 получается как x0+d1. Затем находится невязка этого решения r1= b - Аxk и вторая поправка d1 – как решение системы LUd2= r1 и т.д.

Если произведение LU близко к А, то норма ||Е – (LU)A-1|| мала, и процесс сходится очень быстро при условии, что вычисления проделываются точно. Если они проделываются с той же точностью, с какой было найдено LU-разложение, то ни к какому уточнению они не приведут, так как в этом случае все приближения имеют ошибку такого де порядка, как и ошибка начального приближения.

Практически это означает, что при итерационном уточнении вычисления должны проделываться с удвоенной точностью. Как показывает более детальный анализ особенно важна точность при вычислении невязок и прибавлении поправок. Если эти вычисления проделываются с точностью 2q разрядов (что может быть сделано с использованием режима накопления), а остальные вычисления производятся с q-разрядной точностью, то в результате итерационного уточнения может быть получено истинное решение, округленное до q разрядов.

Покажем, что сходимость итерационного уточнения зависит от обусловленности матрицы А и точности полученного разложения. Пусть произведение вычисленных матриц L и U удовлетворяет равенству LU=A+G. Тогда

(LU)-1А=(А+G)-1А=(E+А-1G)-1.

Предполагая, что ||А-1|| ∙ ||G|| < 1, мы можем представить эту матрицу в виде ряда

E - A-1G + (А-1 G)2 + …

Каждая частичная сумма этого ряда по норме не превосходит соответствующей частичной суммы ряда из норм, и мы получаем

Мы предположили уже, что ||А-1|| ∙ ||G|| < 1, т.е. θСE(А) < 1. При этом предположении предыдущее условие означает, что θСE(А)<.

Конечно, итерационное уточнении возможно и в том случае. Когда известно не LU-разложение, а какое-либо другое разложен, например QR-разложение

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

В общем неявном методе просто итерации важно, чтобы матрица B была легко обратимой. Выберем ее треугольной. Если диагональные элементы матрицы А отличны от нуля, то нижняя треугольная матрица

=

(получаемая из А заменой наддиагональных элементов на нули) будет невырожденной. Метод Зейделя, или метод последовательных смещений, состоит в применении формулы (4) при τ=1 и В =, то есть

 (xk+1 - xk)+Axk=b, или

xk+1 +Uxk=b, (7)

Где матрица U=A- отличается от А тем, что элементы на диагонали и ниже заменены на нули. Формула (7) позволяет легко вычислить xk+1 по xk.

Согласно предложению 1 метод Зейделя сходится тогда и только тогда, когда все характеристические числа матрицы Е - -1А= - -1U по модулю меньше единицы. Легко проверить, что эти числа совпадают с конями уравнения

det(U+λ)=0. (8)

Предложение 4. Для сходимости метода Зейделя достаточно, чтобы матрица А была симметричной и положительно определенной.

Метод Зейделя сходится быстрее, чем метод Якоби, и требует меньшего объема памяти. Последнее обстоятельство связано с тем, что при использовании треугольных матриц, после того как вычислена i-я компонента вектора xk+1, соответствующая компонента вектора xk становится ненужной (см. формулу (7)).

Далее мы рассмотрим прием ускорения сходимости метода Зейделя при помощи введения параметра.

1.5 Метод верхней релаксации.

Разобьем матрицу А на три слагаемых А=L+D+U. Матрица D, как и выше, есть diag (a11, … , ann), а L и U получаются из А заменой на нули элементов aik при i ≥ k и при k ≤ i соответственно. Таким образом, матрица  равна L+D. Будем предполагать, что det D ≠ 0. Метод верней релаксации определяется формулой (4) при условии τ = ω и В=D+ ωL. Формула (4) принимает вид

(D + ωL)(xk+1 – xk)+ ωАхk= ωb.

или

(D + ωL) xk+1 =[(1 – ω) D – ωU]хk= ωb. (9)

При ω = 1 мы получаем отсюда формулу (7) – метод Зейделя.  Применяя предложение 1, мы видим, что метод верхней релаксации сходится тогда и только тогда, когда спектральный радиус матрицы

P=E – (D + ωL) -1ωА

меньше единицы. Иначе матрицу Р можно представит в виде (D + ωL) -1=[(1 – ω) D – ωU].

Характеристическое уравнение матрицы Р можно преобразовать следующим образом:

det (Р - λE) = det (D + ωL) -1 det=[(1 – ω) D – ωU – λ(D + ωL)].

Отсюда видно, что характеристические числа матрицы Р совпадают с корнями уравнения

det=[(1 – ω) D – ωU – λ(D + ωL)]=0. (10)

Введем в уравнении (10 вместо переменной λ переменную ξ, связанную с λ соотношением

.

Легко увидеть, что условие | λ | < 1 равносильно условию Re ξ < 0, а уравнение (10) перейдет в

det [ - ωAξ – (2 – ω) D + ω (U - L)]=0. (11)

Мы получили

Предложение 5. Метод верхней релаксации сходится тогда и только тогда, когда вещественные части всех корней уравнения (11) отрицательны.

Это позволяет получить следующее достаточное условие.

Предложение 6. Для сходимости метода верхней релаксации достаточно, чтобы матрица А была симметричной и положительно определенной и чтобы ω ϵ (0, 2).

Для доказательства напишем уравнение (11) для симметричной матрицы А и рассмотрим корень ξ0 этого уравнения. Для ξ0 существует (вообще говоря, комплексный) ненулевой столбец x такой, что

[– ωА ξ0 – (2 – ω)]D + ω (U–L)]x=0,

и потому

– ω ξ0Ах – (2 – ω) Dx+ ω  (U – L)x=0. (12)

Матрица U – L кососимметрична, и для нее мы имеем

(U – L)x=( –  (U – L)x) T = –(U – L) = – (U – L)x.

Поэтому последний член в равенстве (12) имеет нулевую вещественную часть. Аналогично доказывается, что Ах и Dx вещественны. Кроме того, если А положительно определена, то все ее диагональные элементы положительны, и квадратичная форма Dx также положительно определена. Приравнивая нулю вещественную часть (12), имеем

 (13)

Если ω ϵ (0, 2), то (ω – 2)/ ω < 0. Отсюда следует, что Re ξ0<0. Предложение доказано.

2. Решение системы линейных уравнений методом Якоби

2.1 Условие сходимости итерационного процесса.

 Рассматривается система Ax = b. 

Для применения итерационных методов система должна быть приведена к эквивалентному виду x=Bx+d. Затем выбирается начальное приближение к решению системы уравнений 

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

Метод Якоби.

Самый простой способ приведения системы к виду удобному для итерации состоит в следующем: из первого уравнения системы выразим неизвестное  x1, из второго уравнения системы выразим  x2, и т. д. В результате получим систему уравнений с матрицей B, в которой на главной диагонали стоят нулевые элементы, а остальные элементы вычисляются по формулам:

,    i, j = 1, 2, ... n.

Компоненты вектора d вычисляются по формулам:

,   i = 1, 2, ... n.

Расчетная формула метода простой итерации имеет вид

,

или в покоординатной форме записи выглядит так:

,  i = 1, 2, ... m.

Критерий окончания итераций в методе Якоби имеет вид:

 ,   где   .

Если  , то можно применять более простой критерий  окончания итераций

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

Пусть дана система уравнений:    

Требуется найти решение системы с точностью   

Приведем систему к виду удобному для итерации:

Выберем начальное приближение, например,      - вектор правой части.

Тогда первая итерация получается так:   

Аналогично получаются следующие приближения к решению.

 ,         ,        

Найдем норму матрицы .  Будем использовать норму .

Так как сумма модулей элементов в каждой строке равна 0.2, то  = 0.2 < 1/2, поэтому критерий окончания итераций в этой задаче .

Вычислим нормы разностей векторов:    .

Так как  ,  заданная точность достигнута на четвертой итерации.

Ответ:  x 1 = 1.102,  x 2 = 0.991,  x 3 = 1.101

ЗАКЛЮЧЕНИЕ

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

Все поставленные задачи были выполнены. Цели достигнуты.

1. Бакельман И.Я. Аналитическая геометрия и линейная алгебра [Текст] / И.Я. Бакельман – М.: Просвещение, 1976. – 288 с.: ил.
2. Беклемишев Д.В. Дополнительные главы линейной алгебры [Текст] / Д.В. Беклемишев – М.: Наука. Главная редакция физико-математической литературы, 1983. – 336 с.
3. Беллман Р. Введение в теорию матриц [Текст] / Р. Беллман – М.: Наука, 1969. – 375 с.
4. Забрейко П.П., Таныгина А.Н. Функции от матриц и коммутативные матричные подалгебры [Текст] / П.П. Забрейко, А.Н. Таныгина. – Минск: БГУ, 2011. – 95 с.
5. Кострикин А.И., Манин Ю.И. Линейная алгебра и геометрия [Текст] / А.И. Кострикин, Ю.И. Манин. – Москва, 1980. – 309 с. 
6. Ланкастер П. Теория матриц [Текст] / П. Ланкастер – М.: Наука. Главная редакция физико-математической литературы, 1973. – 280 с.
7. Малугин В.А. Линейная алгебра [Текст] / В.А. Малугин – М.: Эксмо, 2006. – 215 с. 
8. Мальцев А.И. Основы линейной алгебры: учебное пособие для студентов университетов [Текст] / А.И. Мальцев – М.: Наука, 1970. – 400 с.: ил.
9. Стренг Г. Линейная алгебра и ее применения [Текст] / Г. Стренг – Изд-во: Мир, 1980. – 459 с.
10. Тыртышников Е.Е. Матричный анализ и линейная алгебра: Учебное пособие [Текст] / Е.Е. Тыртышников – Москва, 2004-2005. – 372 c.