Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 35
Текст из файла (страница 35)
4. Следует отметить, что в данной главе оказались практически не отраженными прямые методы решения систем уравнений с разреженными матрица— ми (исключение составляет ~ 5.9, посвященный методу прогонки). Желающим найти доступное изложение современных прямых методов, предназначенных для решения очень больших линейных систем с разреженными матрицами, можно посоветовать обратиться к [40]. Укажем также на книги [30], [63], [94], специально посвященные технологии разреженных матриц.
173 Глава 6 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ Системы линейных алгебраических уравнений можно решать как с помощью прямых, так и итерационных методов. Для систем уравнений средней размерности чаще используют прямые методы. Итерационные методы применяют главным образом для решения задач большой размерности, когда использование прямых методов невозможно из-за ограничений в доступной оперативной памяти ЭВМ или из-за необходимости выполнения чрезмерно большого числа арифметических операций.
Большие системы уравнений, возникающие в приложениях, как правило, являются разреженными. Методы исключения для решения систем с разреженными матрицами неудобны, например, тем, что при их использовании большое число нулевых элементов превращается в ненулевые и матрица теряет свойство разреженности. В противоположность им при использовании итерационных методов в ходе итерационного процесса матрица не меняется, и она, естественно, остается разреженной.
Большая эффективность итерационных методов по сравнению с прямыми методами тесно связана с возможностью существенного использования разреженности матриц. Применение итерационных методов для качественного решения большой системы уравнений требует серьезного использования ее структуры, специальных знаний и определенного опыта. Именно поэтому разработано большое число различных итерационных методов, каждый из которых ориентирован на решение сравнительно узкого класса задач, и существует довольно мало стандартных программ, реализующих эти методы. В этой главе будут рассмотрены наиболее простые и известные итерационные методы, позволяющие решать достаточно "нирокий класс систем.
174 $6.1. Метод простой итерации 1. Приведение систваы к виду, удобному дли итераций. Для того чтобы применить метод простой итерации к решению системы линейных алгебраических уравнений (6.1) х= Вх+ с. (6.2) Здесь  — квадратная матрица с элементами Ь,~ (3, 1 = 1, 2, ..., ш), с— вектор-столбец с элементами с; (1 = 1, 2, ..., пз). В развернутой форме записи система (6.2) имеет следующий вид: х1 = Ь11х1 + Ь1 гхоз + Ь13хз + ." + Ь1тхт + с1, хг = Ь21х1 + Ьггхг + Ьгзхз + ... + Ьгтхт+ сг (6.3) х = ЬтЛ+ Ьтгхг+ Ьтзхз+ " + Ь хт+ ст, Вообще говоря, операция приведения систслм к аиду, удобно.ау для итераций (т.е. к виду (6.2)), не является простой н требует специальных знаний, а также существенного использования специфики системы. В некоторых случаях в таком преобразовании нет необходимости, так как сама исходная система уже имеет вид (6.2), Самый простой способ приведения системы к виду, удобному для итераций, состоит в следующем.
Из первого уравнения системы (6.1) выразим неизвестное х1.. х1 — — а11 (Ь1 а1гх'г а1зхз " а1тхт) нз второго уравнения — неизвестное хг.. хг а22 (Ь2 а21х1 агзхз " а2тхт) -1 н т.д. В результате получим систему Х1 Ь1гзг + Ь13ХЗ + °" + Ь1,т-1%и"1 + хг = Ь21х1 + Ьг з~Ъ + " + Ьг, -1 хт-1 + хз Ь31х1 + Ьзгхг + "+ Ьз,т-1%и-1 + Ь1тхт + с1, Ьгтхт + сг Ьзтхт+ сз (6,4) = Ь 1х1 + Ь гхг + Ьтзхз + ... + 6 1ът + ст в которой на главной диагонали матрицы В находятся нулевые элементы.
Остальные элементы выражаются по формулам 175 с квадратной невырожденной матрицей А, необходимо предварительно преобразовать эту систему к виду Ь() — -афа<ь с; = Ь(/а<< (г', /' = 1,2, ..., т, 1 Х г). (6.5) вычисляя полученное выражение, находим первое приближение х( 1) — Вх( 0) + Подставляя приближение х(!) в правую часть системы (6.2), получим х(2) = Вх<1) + Продолжая этот процесс далее, получим последовательность х<о), х(1), ..., х<"', ...
приближений, вычисляемых по формуле х</с+" =Вх<"'+ с, 1=0,1,2, ... В развернутой форме записи формула (6.6) выглядит так: (6.6) х! Ь11х1 + Ь12х2 + Ь13х3 + -" + Ь1ах + с1~ (/с+1) (/с) ( Ь) < /с) < /с) х2 Ь21х1 + Ь22х2 + Ь23х3 + ." + Ь23гхщ + с2, ( /с~)) ( /с) ( /с) ( И ( /с) (6.7) " = Ьщ х' ' + Ь„х' ' + Ь Зх' ' + + Ь х' ' + В случае, когда для итераций используется система (6.4) с коэффициентами, вычисленными по формулам (6.5), метод простой итерации принято называть методом Якоби'.
3. Огодимость метода простой итерации. Т е о р е м а 6.1. 1Хусть выполнено условие 1В1 < 1. (6.8) Тогда: 13) региение х системы (6.2) существует и единственно; 2о) при произвольном начальном прибли)кении х(о) метод простой итерации сходится и справедлива оценка погрешности 1 Карл Густав Якоб Якоби (1804 — 1851) — немецкий математик. 176 Конечно, для возможности выполнения указанного преобразования необходимо, чтобы диагональные элементы матрицы А были ненулевыми.
Часто систему (6.1) преобразуют к виду х = х — т(Ах — Ь), где т— специально выбираемый числовой параметр (см. п. 5), 2. Описание метода. Выберем начальное приближение х< о) = = (х,'о', х'о), ..., х'()) Р. Подставляя его в правую часть системы (6 2) и ~х(п> Ц ь 1В~п~х(О> (6.9) х> ~+» — х = З (х> >'> — х), (6.10) Вычисляя норму левой и правой частей этого равенства и используя неравенство 1В (х~ "> — х)~ ~ 1З~~Ы>'> — х~, имеем 1х'~ >> — х~ 4 ~В~1х' "' — х~. Так как это неравенство верно для всех х ~ О, то 1х(~> х~ ~ 1В~~х(»->> х~ ~ 1Щ2~х(п-2> х~ ь 4: ~ ~В~»->~ »> ~ ~ 1В~»~ ~»> Справедливость неравенства (6.9) установлена.
Учитывая, что ~х'®> — х~ не зависит от», а ~В~" ~ О при» ~ оо, получаем из него, что 1х' "> — х~ 0 при» -~ со. йй> 3 а м е ч а н и е 1. Теорема 6.1 дает простое достаточное условие (6.8) сходимости метода простой итерации. Грубо это условие можно интерпретировать как условие достаточной малости элементов 5; матрицы В в системе, приведенной к виду (6.2). 3 а м е ч а н и е 2. Если 1В~ = 1В1„, то условие (6.8) принимает вид ~В~ = шах Х ~Ь;>~ < 1. 1~ >~т> Для метода Якоби это условие в силу равенств 5п = О, 6;~ — -афан эквивалентно условию диагонального преобладания (5.45).
Если же воспользоваться условием (6.8) при 1В~ = ~В~и то для метода Якоби получим другое условие диагонального преобладания: (6.11) Х ) а;>~ с ~ а1>~, > = 1,2, ..., и>. Ы1 >Фу 177 и 1с. Из курса линейной алгебры известно, что система линейных алгебраических уравнений имеет единственное решение при любой правой части тогда и только тогда, когда соответствующая однородная система имеет только нулевое решение.
Пусть х — решение однородной системы х = Вж Тогда ~х~ = ~Вх~ < ~В~ ° 1х1. Так как по условию ~В~ ( 1, это неравенство возможно только при 1х~- = О. Следовательно, х = О и тем самым первое утверждение теоремы доказано. 2с. Вычитая из равенства (6.6) равенство х = Вх+ с, получим Таким образом, для сходимости метода Якоби достаточно, чтобы матрица А была близка к диагональной. 3 а м е ч а н и е 3.
Из оценки (6,9) следует, что при выполнении . условия (6.8) метод простой итерации сходится со скоростью геометрической прогрессии, знаменатель которой <1 = 1В~. Скорость сходимости тем выше, чем меньше величина 1В1. Хотя метод сходится при любом начальном приближении х«», из оценки (6.9) можно сделать полезный вывод: начальное приближение желательно выбирать близким к решению. 3 а м е ч а н и е 4. Оценка погрешности (6.9) является априорной. Ее использование для формулировки критерия окончания итераций затруднительно, так как значение ~х<ш — х~ неизвестно, а его грубое оценивание заведомо приведет к завышению необходимого числа итераций. 4. Апостериорная оценка погрешностям. П р ед л о ж е н и е 6.1.
Если аыпо<пеяо условие (6.8), то справедлива апостериорная о<<спха по<решности ~х< и> х~ ( М ~х<п> х<п-1> ~) 1 (6.12) а Запишем равенство (6.10) при а = и — 1 в виде х' "' — х = В (х< и " — х< "') + В (х< "> — х). Тогда 1х< "> — х~ = "1 В (х< " " — х< "> ) + В (х< "> — х) ~ 4 1)~ И~ $х<" '> — х'"> /~ + 1В<[1х<п> — х~. 3 а м е ч а н и е. Величину, стоящую в правой части неравенства (6.12), можно легко вычислить после нахождения очередного при- ближения х< "'. Если требуется найти решение с точностью к, то в силу (6.12) сле- дует вести итерации до выполнения неравенства '><х<п> х< и » ~ ( 1Н 1 178 Для завершения доказательства достаточно заметить, что полученное неравенство эквивалентно неравенству (6.12).
И Таким образом, в качестве критерия окончания итерационного процесса может быть использовано неравенство ~х(п) х(и-1) ~ ~ е (6.13) — 14 де е, = — (И вЂ” е. В практике вычислений иногда используют привлекательный своей простотой критерий окончания 1Х(а) — х(п-1) 1 ( Е. (6.14) Отметим, что для метода простой итерации его применение обосновано только тогда, когда 1В~ <1/2 (в этом случае (1 — 1В1)/1В~ > 1 и выполнение неравенства (6.14) влечет за собой выполнение неравенства (6.13)). Однако в большинстве реальных случаев величина 1В~ оказывается близкой к единице и поэтому (1 — 1В$)/1В$ < 1. В этих случаях е) < е и использование критерия (6.14) приводит к существенно преждевременному окончанию итераций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
