IV Канатников А.Н., Крищенко А.П. Линейная алгебра (Зарубин В.С., Крищенко А.П. - Комплекс учебников из 21 выпуска), страница 46

Общее представление об одношаговых методах дает мешод просщоб итперавва решения нелинейного уравнения 1(х) = О, в котором у (х) — произвольная функция одного действительного переменного [1Ц. Для применения этого метода нужно уравнение преобразовать к виду х = у(х). Отправляясь от некоторого начального приближения хе, строят юпераииоипую последовательностпь (х,Д согласно формуле хн+1 = у(хн), Ж = О, 1, 2,... Если эта последовательность сходится к некоторому значению х„т.е. ~хн — х, ~ -+ 0 при Ф -+ оо, а функция у(х) непрерывна в точке х„то, переходя в равенстве хь1+1 = у(хл1) к пределу при Ф -+ со, заключаем, что х, = у(х,) и значение х, является искомым решением уравнения 1(х) = О.

В качестве приближе- 309 11.3. Описание итерационных методов Каноническая форма одношаговых методов. Наиболее употребительные одношаговые итерационные методы решения СЛАУ укладываются в единую схему, согласно которой итерационная последовательность (х~), построенная по такому методу, подчиняется уравнению общего вида х~+1 — х~ Ви+1 + Ах~ = Ь, т1е+1 (11.5) в котором йе1 В1е+1 ф О, М = О, 1, ... Уравнение (11.5) называют канонической формой одношагоеоео итерационноео метподо. Выбор невырожденных матриц В1е+1 характеризует конкретный метод, ипхераиионный нарамеепр т1е+1 не является обязательным (его можно было бы учесть в матрице В1я+1) и вводится в уравнение иэ ния точного решения х, берут одно из значений х1е, достаточно 'близкое к х,.

Аналогично можно поступить и в случае решения СЛАУ Ах = 6 с невырожденной матрицей А. Преобразовав СЛАУ в эквивалентную ей систему вида х = Ф(х) = Вх+ с, мы можем построить итерационную последовательность х~+1 = Ф(х~), Ф = О, 1,..., начав с некоторого начального столбца х (индексы в нашем случае удобнее ставить вверху, а не внизу, оставляя нижний индекс для нумерации элементов матриц и столбцов). Сходимость такой последовательности, состоящей из столбцов, или элементов пространства Ко, следует рассматривать относительно некоторой нормы.

Последовательность (х~) сходится к некоторому столбцу х', если )~х~ — х')! -+ 0 при М -+ оо. Векторная функция Ф(х) = Вх+ с непрерывна в любой точке х' Е 1я", и мы можем перейти к пределу под знаком непрерывной функции: х' = Вх'+с. Таким образом, предел итерационной последовательности дает нам точное решение СЛАУ, а в качестве приближенного решения системы можно взять подходящий столбец итерационной последовательности.

ЕЬ ИТЕРАЦИОННЫЕ МЕТОДЫ Методы Якоби и Зейделя. Представим невырожденную матрицу А в виде суммы трех матриц (11.6) А=А +Р+А~, где Р— диагональная матрица; А и А~ — соответственно нижняя и верхняя треугольные матрицы с нулевыми элементами на диагонали. Такое представление существует и единственно, так как в каждой позиции только одна из складываемых матриц имеет ненулевой элемент, равный соответствующему элементу матрицы А.

Матрица А содержит элементы А, расположенные под главной диагональю, матрица А~ — элементы над главной диагональю, а матрица Р— диагональные. соображений удобства. Его используют для поиска путей усиления конкретного метода с точки зрения сходимости итерационной последовательности и скорости этой сходимости. В канонической форме одношагового итерационного метода изменение хА"+1 — х~ текущего столбца фактически связывается с неелзкоб 6 — Ах~, которую дает этот столбец в рассматриваемой СЛАУ. Чем меньше невязка, тем меньше изменение текущего столбца.

Матрица Ву~.м реализующая эту связь на Ф-м шаге, должна быть достаточно простой, так как, согласно канонической форме метода, для получения изменения хн+~ — х~ требуется вычисление обратной матрицы для Вн.~|. Если это не так, то более простым может быть обращение матрицы А, и тогда прямой метод решения СЛАУ окажется более предпочтительным. Если в канонической форме (11.5) одношагового итерационного метода матрица В,ч+1 является единичной, то итерационный метод называют *внььм, а иначе — мелевым. Если матрицы Вн+1 и итерационный параметр тн+1 от номера итерации не зависят: Вн+1 = В, тн.~~ = т, то метод называют стационарным.

зп 1К3. Оииеаиие итераииоиимх методов Пример 11.1. Для квадратной матрицы 1 -3 1 2 2 0 6 -1 3 — 3 -2 -7 -1 — 2 4 5 четвертого порядка в представлении (11.6) имеем 0 0 0 0 1 0 0 0 2 0 0 0 0 0 0 0 3 -3 0 0 ' 0 0 -2 0 -1 -2 4 0 0 0 О 5 0 — 3 1 2 0 0 6 — 1 0 0 0 — 7 0 0 0 0 В СЛАУ Ах = Ь вместо матрицы А подставим ее представление (11.6). Получим (А + Р+ А+)х = Ь, откуда Рх=-(А +А+)х+Ь. (11.7) Если диагональные элементы матрицы А = (а;.) не равны ну- лю, то диагональная матрица Р = йая(ам, аоэ, ..., а„„) имеет обратную матрицу Р 1 = Йаб (а111, а~~~, ..., а,,1).

В этом слу- чае систему (11.7) можно записать в виде х= — Р '(А +А+)х+Р 'Ь. (11.8) Систему (11.8) можно использовать для построения итерационной последовательности х~+1=-Р '(А +А+)х~+Р 'Ь, И=0,1,..., (11.9) где хе — произвольное начальное приближение. Вычисление решения СЛАУ при помощи указанной последовательности 312 |1. ИТЕРАЦИОННЫЕ МЕТОДЫ называют метводом Якоба. Матричные соотношения (11.9) несложно записать в координатной форме. Обозначая номера строк и столбцов индексами внизу, получим з-! в х; + = — Я а,"х.

— ~) аух. +6;), !'=1,н. (11.10) |=! !=в+! (Р+А )х= — А+х+6. (11.11) Если диагональные элементы матрицы А не равны нулю, то нижняя треугольная матрица Р+ А имеет обратную матрицу (Р+А ) ! и систему (11.11) эквивалентна следующей: х=(Р+А ) '(-Атх+Ь). (11.12) Соотношение (11.12) можно использовать для построения ите- рационной последовательности х + = (Р+А ) |( — А+х~+6), (11.13) использование которой для решения СЛАУ Ах = Ь называют метводом Зекделл.

Для вычисления итерационной последовательности в методе Зейделя требуется обращение нижней треугольной матрицы Р+ А, но оказываетсл, что такое обращение является формальным. Преобразуем соотношение (11.13): Рх +' =-А х~+' — А+х~+6. Исходя из этой формы уравнения, получаем !-! И х! + = — ~-~~> аух~~+ — ~~! ея хр+6;), !'=1,к.

(11.14) 3=! |=!+! Здесь и далее мы условимся считать равными нулю суммы, у которых верхний предел суммирования меньше нижнего. Используя представление (11.6) матрицы А, запишем СЛАУ Ах = 6 в следующем виде: П.З. Описание итерационных методов В уравнениях (11.14) элементы х~+ столбца х~+~ находятся и в левой, и в правой части. Однако если их вычислять последовательно для 1 = 1, 1 = 2, ..., е' = и, мы увидим, что в формуле для очередного элемента х, + используются только уже наиденные элементы х +1, ..., х, + .

Обращение матрицы Р+ А естественным образом встроено в вычислительную схему и не требует отдельных усилий. Вычислительные схемы методов Зейделя и Якоби, которые описываются уравнениями (11.10) и (11.14), очень похожи. Различие лишь в том, что при вычислении каждого элемента столбца х +1 в методе Якоби используются только элементы предыдущего столбца х~, а в методе Зейделя более новые уже найденные элементы текущего столбца. И метод Якоби, и метод Зейделя могут быть получены в рамках канонической формы (11.5) одношаговых итерационных методов. Итерационная последовательность метода Якоби подчиняется уравнению Рх~+' = — (А + А+)т~ + 6, которое эквивалентно (11.9). Это уравнение легко преобразуется в форму Рх~+' = — (А — Р)х~ + 6, откуда получаем Р(х + — х )+Ах~ =6.

Видим, что для получения метода Якоби в канонической форме надо положить Вы+1 — — Р, г,е+1 = 1. Таким образом, метод Якоби можно квалифицировать как одношаговый неявный стационарный итерационный метод. Из уравнения (11.13) находим (Р+ А )я~+1 = — А+я~+ Ь, или, заменяя матрицу А+ через матрицу А, (Р+ А )хи+1 = = — (А — Р— А )хн +Ь. Следовательно, (.Р + А ) (х + — х ) + Ах~ = 6. (11.15) Для представления метода Зейделя в канонической форме мы должны положить Ву+1 = Р + А, ты+1 = 1, М = О, 1, ...

Та- ким образом, метод Зейделя также относится к одношаговым стационарным неявным методам. 314 11. ИТЕРАЦИОННЫЕ МЕТОДЫ Другие итерационные методы. Полагая в канонической форме итерационных методов В1т+1 = Е, ттт» 1 — — т, И = О, 1,..., получаем уравнение х~+1 — х~ +Ахи =Ь, т (11.18) дающее мешод нростпой инзерации, представляющий собой явный стационарный метод.

Обобщением метода простой ите. рации является метнод Ричардсона, для которого в канонической форме (11.5) итерационных методов следует положить Вн» 1 = Е. В результате получим х~+1 — х~ +Ах~ =Ь. тж+1 (11.17) В уравнение (11.15) метода Зейделя введем числовой параметр ис х~+1 - х~ (О+ыА-) +Ах =Ь. (11.18) Это приведет к серии методов, среди которых находится и метод Зейделя, соответствующий частному случаю и = 1. Скорость сходимости итерационной последовательности зависит от параметра ю, подбирая который можно получить метод, более точный по сравнению с методом Зейделя.