Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 37
Текст из файла (страница 37)
После приведения системы к виду (6.16) убеждаемся, что 1В)) < поэтому в силу теоремы 6.2 метод Зейделя сходится. Положим х'о' = (О, О, 0)т и будем вычислять последовательные приближения по формулам Первое уравнение задает на плоскости х)Охг прямую 11, второе — пря- мую 1г (рис.
6.1). Расчетные формулы метода принимают вид 016хг(~) О'08хз()') + 12 — О. 424х( "' — 1.736, (А 1)— 1 Й2"' = 0.2х 1 хз()(") = -0.1389х', "+1' — 0.5889т' "+1) — 0.0667. Здесь и ~Вг~„= ОА24. Будем вести итерации до выполнения критерия окончания 16,30), где аг = 10 3 (1 — 0.7278)/0.424 (3 0.64 10 3.
Значения приближений с четырьмя цифрами после десятичной точки приведены в табл. 6.2. Таблица62 х( ))) 1 1.2000 0.0000 0.9088 х( ") г 0.0000 х( ))) 3 ~х())) ( о-1) ~ 0.0000 0.8040 -1.9938 0.9958 0.0125 0,8013 0.8004 0.8001 х( о) г -1,9980 -1,9998 (и) 3 ~х())) ( и-1) ~ 0.9995 0,9998 0.9986 0.0005 0.0041 0,0014 Прн и = 8 критерий окончания выполняется и можно положить х) = = 0.800 т 0.001, хг = -2.000 х 0.001, хз = 1.000 х 0.001. Заметим, что в действительности решение с точностью е = 10 3 было получено уже при и = 7.
186 0 0.16 -0.08 Вг = 0 О -0.424 0 О 0 -1.4960 -1.8288 0.6476 0,8841 1.4960 0,3328 0.8367 0,8121 -1.9435 -1.9813 0.9616 0.9873 0.1147 0.0378 3 а м е ч а н и е. Существует устойчивое зас)луждение, связанное с представлением о том, что метод Зейделя сходится быстрее, чем метод Якоби. Это действительно так, если матрица А симметрична и положительно определена (мы убедились в преимуществе метода Зейделя для системы уравнений с такой матрицей, решая примеры 6.1 и 6.2).
Однако в общем случае возможны ситуации, когда метод Якоби сходится, а метод Зейделя сходится медленнее или вообще расходится. Возможны и противоположные ситуации. Дело в том, что эти методы ориентированы на решение разных классов систем: метод Якоби — на системы с матрицами, близкими к диагональным, а метод Зейделя — на системы с матрицами, близкими к нижним треугольным. ~ 6.3. Метод релаксации Метод последовательной верхней релаксации является одним из наиболее эффективных и широко используемых итерационных методов для решения систем линейных алгебраических уравнений с симметричными положительно определенными матрицами А.
Этот метод часто называют ЗОВ-методом). Частично популярность БОК-метода можно объяснить его простотой и тем, что он хорошо известен широкому кругу прикладников. Суть иегпода релаксации состоит в следующем. После вычисления очередной ))'-й компоненты (Й + 1)-го приближения по формуле метода Зейделя 6')х) + 6тх2 + ... + 61 (-)х(-1 + 6( (+)х(+1 + -( В+1), ()(+1) ()г+1) ()(+1) ( Й) +...+ 6,,„х„+с; (Ь производят дополнительно смещение этой компоненты на величину (() — 1)(х', ' — х( '), где а) — пара)иетр релаксации. Таким образом, (-я компонента (6 + 1)-го приближения вычисляется по формуле х', ' = х', ' + (ы — 1)(х', — х, ) = ь)х; + (1 -())х; На рис.
6.2 показано несколько первых итераций метода при значении параметра релаксации () = 1.25. 1 От англ. эиссеэе)че обжег ге1аха1)оп. 187 В обозначениях предыдущего параграфа компактная формула для вычисления х< ""~ > записывается следующим образом: х< "+~> = (1 — и)х~ Ь' + шВ~х~"'~~ + ыВ2х' "~ + ыс. Как нетрудно видеть, при ы = 1 метод релаксации совпадает с методом Зейделя. При и > 1 его было принято называть методов последоеатпеяъной верхней ре*аксации, а при ы ( 1 — методов воследователъной нижней реаахсации. В последнее время метод релаксации называют методом последовательной верхней релаксации для любых значений ы. Если А — симметричная положительно определенная матрица, то при любом значении параметра ы (О < ~ < 2) метод релаксации сходится.
Часто оказывается возможным выбрать параметр ~ > 1 так, чтобы БОК-метод сходился существенно быстрее, чем методы Якоби и Зейделя. Однако выбор параметра релаксации — довольно трудная задача. Во многих случаях она решается экспериментальным путем. Существуют различные модификации метода релаксации. Распространенный вариант метода связан с использованием различных параметров ы; для вычисления различных компонент х; очередного (Й + 1)- го приближения к решению.
Пример В.З. Используя метод последовательной верхней релаксации с параметром ы = 1.12, найдем решение системы (6.15) с точностью е = 10 з. 188 Приведем систему к виду (6.16), положим х< о' = (О. О, 0)т и будем вычислять последовательные приближения по формулам: х<" '» = (1 — <о)х<»»с» + <о (0.16хг< "» — 0.08хз<~» + 1.2), хг<~+»» = ш 0.2х'"'<' + (1 — а»)хг<"' + <о (-0.424хз'"' — 1.736) зз" '» = <о (-0.1389х< "'»» — 0.5889хг'"'" ) + (1 — <о)хз'"' — <о 0.6667 Значения приближений с четырьмя цифрами после десятичной точки приведены в табл, 6.3. Таблица6.3 и 0 1 2 3 4 5 х' "» 0.0000 1.3440 0.8166 0.8094 0.7995 0.8001 х< "» 0.0000 -1.6433 -1.9442 -1.9973 -1.9998 -2.0000 2 хз<™ 0 0000 0'8001 0 9846 0.9986 1.0001 1.0000 Сравнение с точным решением х» = 0.8, хг —— -2, хз = 1 показывает, что для получения приближения к решению с точностью е = 10 з потребовалось всего 4 итерации.
Напомним, что для достижения той же точности при том же начальном приближении методами Якоби и Зейделя потребовалось соответственно 13 и 7 итераций. $6.4. Дополнительные замечания » Корнелий Ланцош (1893 — 1974) — физик-теоретик и математик. Родился в Венгрии. Работал в Германии, США, Ирландии. 189 1. При изложении итерационных методов решения систем линейных алгебраических уравнений нам пришлось ограничиться простейшими методами. В данной главе оказались не рассмотреннымси такие известные и популярные методы, как метод наискорейшесо спуска, ме»под сопря»<сенньсх срадиентов (назьваемый еще методом дан<зоша»), метод минимальнь<х невлзон линейнь<й мносошасовмй метод с чебышевсним набором параметров и др.
Эти методы изложены, например, в учебниках [9], [71] и в специальной литературе [20], [72], [89]. Отметим, что методы наискорейшего спуска н сопряженных градиентов будут рассмотрены в гл. 10 в связи с задачей минимизации квадратичной функции (6.31). 2. Многие итерационные методы решения систем с симметричными положительно определенными матрицами основаны на замене задачи отыскания решения системы Ак = Ь эквивалентной задачей отыскания минимума квадратичной функции Фф = — (Ат в) (Ь 4 1 (6.31) В частности, метод Зейделя дает ту же последовательность приближений, что и метод покоординатного спуска, примененный к функции (6.31).
Подробнее об этом будет сказано в ~ 10.2; см. также 19]. 3. В настоящее время наиболее глубоко развиты методы решения систем уравнений с симметричными положительно определенными матрицами. Иногда этого достаточно, так как в принципе существует возможность симметризовать любую систему Ак = Ь с невырожденной квадратной матрицей, т.е. свести ее к эквивалентной системе с симметричной положительно определенной матрицей.
Для этого можно умножить обе части системы на матрицу Ат. В полученной таким образом системе (6.32) матрица А = АтА обладает всеми нужными свойствами. Однако указанным образом поступают сравнительно редко. Дело в том, что при переходе от А к А может быть потеряно свойство разреженности. Кроме того, вообще говоря, существенно ухудшается обусловленность системы. На- пример, для матриц, близких к симметричным, созна(А) и (сопд(А))~.
Следовательно, имеется реальная опасность, что система (6.32) окажется очень плохо обусловленной. 4. Как уже было отмечено, одно из важнейших достоинств итерационных методов заключается в возможности эффективного использования разреженности матрицы А. Поясним сказанное на примере метода простой итерации. В случае когда матрица  — заполненная, для вычисления по формуле (6.6) требуется выполнить примерно 2тп2 арифметических операций. Однако для разреженной матрицы с М(М < таад) ненулевыми элементами требуетсн лишь примерно 2М арифметических операций (одно умножение и одно сложение на каждый ненулевой элемент). Таким образом, общее число операций составляет примерно 2Мп (в), где и (ь) — число итераций, необходимое для достижения заданной точности В.
Глава 7 МЕТОДЫ ОТЫСКАНИЯ РЕШЕНИИ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ В этой главе рассматривается задача отыскания решений систем нелинейных уравнений, существенно более сложная, нежели задачи отыскания решения одного нелинейного уравнения или системы линейных алгебраических уравнений. Тем не менее достаточно подробное знакомство с содержанием глав 4 и 6, а также ~ 5.1 — Ь.З позволяет увидеть соответствующие аналогии в постановках проблем и методах их решения для нелинейных систем. Будем считать, что в множестве ~в-мерных векторов введена некоторая норма, порождающая соответствующую норму для квадратных матриц порядка т (см.
~ 5,2). 3 7.1. Постановка задачи. Основные этапы решения 1. Постановка задачи, Задача отыскания решения системы нелинейных уравнений с ~и неизвестными вида является существенно более сложной, чем рассмотренная в гл. 4 задача отыскания решения уравнения с одним неизвестным. Однако на практике она встречается значительно чаще, так как в реальных исследованиях интерес представляет, как правило, определение не одного, а нескольких параметров (нередко их число доходит до сотен и тысяч). Найти точное решение системы, т.е. вектор я = (хь т2, ..., са)т, удов- 191 летворяющий уравнениям (7.1), практически невозможно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
