Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 37
Текст из файла (страница 37)
и! в качестве дополнительной строки матрицы В). Но очевидно, что ~сух(?)=~~~~х(ты 0, так что элементы контрольного столбца равны з=1 " ' ,=1 сумкам остальных элементов, лежаших в той же строке. Вторая часть таблицы дает приближенное решение системы, которое мы получаем, суммируя соответствуюшие компоненты вычисленных векторов. Из сравнения табл. !П,1, Ш. 2 и Ш, 3 с результатом, полученным по схеме единственного деления, мы видим, что сходимость процессз во всех трех вариантах приблизительно одинаковая; 14-е приближение дает в данном примере результат, верный с точностью до единицы четвертого знака. О ~ 1 Лчо) 3.14 4.1332 5.04451 5.044805 1.24 1.6544 1,974961 1.975063 1.975111 0.98 1.2412 0.10 0.1140 1.534769 !.5348?1 1.534920 0.122010 0.122010 0.1220!О 5 044951 Сходимость процесса последовательных приближений можно сильно улучшить, применяя различные приемы ускорения.
Процесс последовательных приближений с применением приемов ускорения сходимости в большинстве случаев укладывается в общую схему итерационных процессов с нарушением стационарности. Целесообразный выбор приемов ускорения требует предварительной информации о расположении собственных значений матрицы. Мы вернемся к этому вопросу в гл. !Х. й 31. Подготонка системы линейных уравнений к виду, удобному для применения метода последовательных приближений. Метод простой итерации Условия схолимости метода последовательных приближений требуют, чтобы матрица коэффициентов системы АХ= Р была, в том или ином смысле, близка к единичной матрице. Если это условие не выполнено нли „плохо выполнено", систему целесообразно пред- ХО) ЛО 2) Лпа) Х(ы) Тапллнл ?П, 3 Вычисление приближений по формуле Л(а) = ВЛ('-') + 6, Х(') = (1, О, О, О)' 0.82 1.1236 1.412761 1.412862 1.412910 8 311 подготоВИА системы линейных ТРАВнений 215 где Н некоторая неособенная матрица, которая выбирается так, чтобы матрица НА была бы близка к единичной, т.
е. матрица Н была бы близка к А '. Применение метода последовательных приближений к подготовленной системе, как было указано, равносильно применению стзционарного итерационного процесса Х~ 1=Х~ !+Н(Р— АХ~" '!) к исходной системе. Выбор матрицы Н может быть осуществлен с использованием частных особенностей данной системы. Рассмотрим некоторые наиболее употребительные способы подготовки, использующие лишь довольно поверхностные сведения о матрице коэффициентов. Пусть матрица А положительно определена.
Тогда система АХ= Р всегда может быть подготовлена к виду, в котором метод последовательных приближений будет сходящимся. Действительно, вычислив, например, первую норму р матрицы А, мы получим, что все собственные значения матрицы А заключены в открытом интервале (О,!А). Положим Н= — Е. 2 Система АХ= Р преобразуется к виду Х=(Š— — А) Х+ — Р = ВХ+Сг. (2) 2 Собственные значения матрицы В = Š— — А будут заключены в открытом интервале ( — 1, 1) и, следовательно.
метод последовательных приближений будет сходящимся. В качестве примера возьмем систему (9) 9 23. Здесь р=2.62. Выполнив вычисления, получим 0.23664122 — 0.32061069 — 0.41221374 0.50381679 В= — 0.32061069 0.23664!22 — 0.24427481 — 0.33587786 — 0.41221374 — 0.24427481 0.23664122 — 0.16793893 — 0.50381679 — 0.33587786 — 0.16793893 0.23664122 0.22900763 0.38167939 0.53435115 0.68702290 (3) варительно подготовить к применению метода последовзтельных приближений. Подготовка состоит в переходе от данной системы АХ= Р и равносильной системе НАХ= НР, 2!6 итвглционныв методы гвшзния линзйных систвм [гл.
ш В $23 было найдено. что решение системы Х=( — 1.2577938, 0.0434873, 1.0391663, 1.4823929)'. В табл. !!!. 4 приведем несколько последовательных приближений. положив Х~) = О. <о) Таблица УП. 4 Вычисление приближений по формуле Х)г) = ВЛ"ь ')+ О. ОЮЮ51Ю $ ц и2293 3 Х.ВЗ2и ~Т Х)о) 0.38167939 0.22900763 0.3577880 1,0287985 0.5057980 1.3075919 1.3045!21 1.0348124 1.0389819 1.0391421 1.3072091 1.3072456 1.3072526 1.039 ! 661 1.4823926 Из приведенных результатов видно, что метод последовательных приближений в даннои случае сходится довольно медленно. В прикладных вопросах часто встречаются системы, в которых диагональные элементы матрицы А значительно преобладают над остальными элементами матрицы.
В этом случае подготовка системы осуществляется так. Перепишем систему АХ= гч в развернутом виде аыхг+ аггхг+ ... + агах„= уг амхг+аггхг+ +аз ." =)г (4) а„,х, + а„гх, + ... + аьвх„= 7„. Поделим каждое уравнение системы (4) на диагональный элемент. Мы получим систему + хи агв и ... + — х„=— аг„Уг агг " ам х,+ — "х,+ аы ап — х,+х,+ а„г а„, — х,+— а„„ аии х,+ ... +х„=— у аич Х!г) Хоп) Х)го) Хио) Хпоо) Х!ы) — ОА055708 — 1.2354227 — 1.2505812 — 1.2574335 — 1.2577475 — 1.2577935 0.0372939 0.0473327 0.0442080 0.0435403 0.0434939 0.0434874 0.5!62869 1 А668834 1.4760729 1.4821 204 1.4823572 5 31! подготоВИА системы линейных уРАВнений или в матричной записи з17 (5) где 71 ац аю а!2 а!а аы ''' ан а ! е О (5) ач! а„ч и„„ ави О а х1Н) Г а х)Ь вЂ” !) а х)Ь-!) 1! ! ~1 !2 2 ''' 1ч ч (7) Описанная модификация процесса последовательных приближений имеет название метода п р о с т о й и т е р а ц и и нли метода Якоби.
Упомянутое преобразование системы (4) в систему (5), очевидно. равносильно умножению системы (4) слева на матрицу о 1 Таким образом, Я=о ', где Е) — диагональная матрица [ац,..., а„„). Отсюда следует, что необходимое и достаточное условие сходимости нроцесса простой итерации состоит в том, что все собственные значения матрииы В= — Š— Е) А ио модулю меньше -1 единицы. Это условие можно представить в другой форме. Именно, 1 — ЕВ1=1 — В-'А — ЕЕ ~ = = ) еГ ' ! )Π— А — '~7е) ) = ( — 1)", ~ е) ! ( ! А — е) + теу ~. Для применения процесса итерации нет неооходимости на самом деле делать преобразование системы (4) в систему (5), Последовательные приближения можно вычислять по формулам: 218 итеРАЦиОнные методы Решения линейных систем (гл.
Иг Таким образом. для сходимости процесса простой итерации необхо- димо и достаточно, чтобы все корни уравнения аой аж ... аьч а21 а22~ ' ' ' и2 ~А — Р+Ю~= =0 (8) апа а„, ... а„„! ~'~ "'~<1 г 2 И. ')),"~ — "' ~ <1 2 2 221йм' (а ) < йй 2 (1=1, 2, ..., п) (,г'=1, 2, ..., п) Здесь знак штрих у суммы показывает, что нри суммировании опускаются значения 1= У. по модулю были бы меньше единицы.
В случае, если матрица А коэффициентов системы симметричная (или эрмитова) с положительными диагональными элементами, необходимому и достаточному условию сходимости метода простой итерации можно придать следующую легко проверяемую форму (Ю. М. Гаврилов 12]). Лля того чтобы метод простой итерации для системы АХ=Е с симметричной матрицей А, имеюгцей положительные диагональные элементы, сходился, необходимо и достаточно, чтобы матрицы А и А=2Р— А (отличаюигиеся друг от друга знаками недиагональных элементов) бали бы положительно- определенными.
Действительно, в этом случае, в силу положительной определенности матрицы Р, все собственные значения матрицы Р 'А вещественны (теорема 11.14). Поэтому для сходимости процесса необходимо и достаточно, чтобы собственные значения матрицы Р А = =Š— (Š— Р 'А) заключались в интервале (0,2), т, е. чтобы собственные значения матриц Р 'А и 2Š— Р 'А были положительны. Но в силу теоремы 11.16 это равносильно положительной определенности матриц А и 2Р— А. Введенные в й 30 достаточные условия сходимости процесса последовательных приближений, будучи применены к системе (б), дают следующие достаточные условия сходимости метода простой итерации: Ф 311 ПОДГОТОВКА СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ 219 прианаками (10) $ ЗО, поло- следующие достаточные при.
Если воспользоваться обобщенными 1 жив рв= —, то мы получим еще ~ а441 ' знаки сходимости простой итерации: ((=1, 2, ..., и) (у=1, 2, ..., и) (10) Допустим теперь, что задана система АХ= 4"'. в которой преобладание главной диагонали не имеет места. Подбор вспомогательной матрицы Н может быть осуществлен, например. грубым обрзщением матрицы А по методу Гаусса. Часто оказывается целесообразным в качестве матрицы Н взять матрицу, обратную к матрице о- ан а„ а„авв авв авв ав, а„ аги ав авв Дв ив ав ан 0 а, ав где Ьв определитель 412! авв В случае, если матрица А симметричная и А = 14+ Я, где 24 поло. жительно-определенная матрица.
обратная для которой известна, Обращение такой матрицы не представляет труда, ибо сводится к обрзщению матриц второго порядка. Именно, 220 итеРационные метОды РешениЯ линейных систем [Гл. (п процесс последовательных приближений, примененный к системе, подготовленной к виду Х= — В '5Х+)ч 'Е. 2 32. Одношаговый циклический процесс Пусть система линейных уравнений АХ=В представлена в виде Х= — ВХ+ О, (1) где В = Š— А, О = Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
