Турчак Л.И. Основы численных методов. Под ред. В.В.Щенникова (1987) (1095857), страница 22
Текст из файла (страница 22)
пРямые методы Из первого уравнения системы (4.17) найдем с с> х = — — х,+ —. 1 ь '- ь' 1 1 С другой сторопы, по формуле (4>18) х, =А,х,+В1. Приравнивая коэффициенты в обоих выражениях для х„получаем А, = — с,/Ь„В, = а,/Ь!. (4А9) Из второго уравнения системы (4.17) выразим х2 через х„заменяя х, по формуле (4,18): а, (А,х2 + В>) + Ь,х, + с1х, = с12. Отсюда найдем — сх.+0 — а В. 2 3 2 2 1 аА +Ь или х,=А,х,+В„ И вЂ” а В.
В2= ' ' ', е,=а А +Ь,. с А 2 > с, Аналогично можно вычислить прогоночные коэффициенты для любого номера 1: 2 (4.20) е; = а,А; , + Ь;, ~ = 2, 3, ..., и — 1. Обратная прогонка состоит в последовательном вычислении неизвестных х;. Сначала нужно найти х„. Для этого воспользуемся выражением (4.18) прп 1= и — 1 и На главной диагонали матрицы этой системы стоят элементы Ь„Ь1, ..., Ь., над ней — элементы с>, с2, ..., с„ под ней — элементы а„аз, ..., а„. При этом обычно все коэффициенты Ь; не равны нулю. Метод прогонки состоит из двух этапов — прямое прогонки (аналога прямого хода метода Гаусса) и обратной прогонки (аналога обратного хода метода Гаусса). с Прямая прогонка состоит в том, что каждое неизвестное х; выражается через х;+, с помощью прогоночных коэффициентов А;, В,: х;=А;х;„+Вь ~=1, 2, ..., и — 1.
(4.18) 183 гл. 4. системы линейных уРАВнепий последним уравнением системы (4 17). Запишем их: х„, = Л„,х„+ В„„ а„х„ , + о„х„ = Ы„. Отсюда, исключая х„„находим Ȅ— а„В„ Ь„+ „А„ Далее, используя формулы (4.18) и выражения для про- гоночных коэффициентов начало (4.19), (4.20), последова- тельно вычисляем все неиз- В вод 1 а„., ь;, с~, а3 вестные х.
„х„„..., х'. Блок-схема решения системы линейных уравнений вида (4.17) -приведена на рис. 18. При анализе алгоритма метода прогонки надо учие-а;А;,+Ь;,А,--с~/е, тывать возможность деления ю; -(а~-'а,В~-1)/и на нуль в формулах (4.20). Можно показать, что при выполнении условия преобс сл-1 да с = ~+1 ладанпя дпагопальных эле- ментов, т. е.
если 1Ь;! ~ нет ~ ~а,~+!с,~, причем хотя бы для одного значения 1 имеет д а место строгое неравенство, деления на нуль не возникает, и система (4.17) имеет единственное решение. Приведенное условие пре- обладания диагональных эле- де . ментов обеспечивает также с>1 1 сБ-1 устойчивость метода прогонНет ки относительно погрешно- стей округлений. Последнее Вывод (хД обстоятельство позволяет использовать метод прогонки для решения больших систем уравнений.
Заметим, Рис. 18. Блок-схема метода что данное условие устойчипрогонки вости прогонки является до- статочным, но не необходимым, В ряде случаев для хорошо обусловленных систем вида (417) метод прогонки оказывается устойчивым да- 5 3, ИТЕРАЦИОННЫЕ МЕТОДЫ же при нарушении условия преобладания диагональных элементов. 5. 0 других прямых методах. Среди прямых методов наиболее распространен метод Гаусса; он удобен для вычислений на ЭВМ. Перечислим некоторые другие методы. Схема Жордина при выборе главного элемента не учитывает коэффициенты тех уравнений, из которых уже выбирался главный элемент,. Она не имеет преимуществ по сравнению с методом Гаусса. Отметим лишь, что здесь облегчается обратный ход, поскольку система приводится к диагональному виду (а не к треугольному).
Эта схема часто используется для нахождения обратной матрицы. Метод квадратного корня используется в тех случаях, когда матрица системы является симметричной. Метод оптил~ального исключения удобен при построчном вводе матрицы системы в оперативную память. Однако построчный ввод имеет и недостатки: частые обращения к внешним устройствам, невозможность выбора главного элемента и др.
Клеточные методы могут использоваться для решения больших систем, когда матрица и вектор правых частей целиком не помещаются в оперативной памяти. Эти и другие методы решения систем линейных уравнений подробно описаны в более полных пособиях по численным методам, а также в специальной литературе по линейной алгебре (см, список литературы). 9 3. Итерационные методы $. Уточнение решения. Решения, получаемые с помощью прямых методов, обычно содержат погрешности, вьтзванпые округлениями при выполнении операций над числами с плавающей точкой на ЭВМ с ограниченным числом разрядов. В ряде случаев зти погрешности могут быть значительными, и необходимо найти способ их уменьшения, Рассмотрим здесь один из методов, позволяющий уточнить решение, полученное с помощью прямого метода.
Найдем решение системы линейных уравнений П1~Х1+ П~2Х2+ ° ° ° + 01 Х = Ь!, Й21х1 + 022х2 + + Я2 х Ь2 (4.21) а„,х,+а„2х,+... + а„„х„= 6„ Гл. 4. системы линеЙных уРАВнепий П сть с помощью некоторого прямого метода вычислены 1 сть (о) (о) (о) приближенные значения неизвестных х1, х2, ..., хп . Подставляя это решение в левые части системы 14.21), (о) получаем некоторые значения Ь;, отличные от Ь, (1 = =1,2,...,п): (о) (о) (о) ),(о) а„х1~ + а12х2 + ... + а1„х„= 61,, (о) (0) (о) у(о) а ~1 + а 2х2 +... + а2~х~ = 2 2 ~4 22) ° В Ф В 1 Э Э ° Ф (о) (о) ,(о) ь(о) а~1т~ + а~от2 + ° ° ° + аппа:и = и Введем обозначения: е; — погрешности значений непз- (0) вестных,г, — певязки, т. е.
(о) Вычитая каждое уравнение системы (4.22) из соответствующего уравнения системы (4.21), с учетом обозначений 14,23) получаем (0) (0) (о) (о) а11~1 + а12~2 + ° ° ° + а1п~п г1 Ф ао,е1 + а22(-'2 + ... + а.„еп = г2, (4.24) (О] ,(0) (0) (0) . (о) . (о) л(о) „(о) ап1".1 + ап2" 2 + ° ° ° + апп 'и и (о) Решая эту систему, находим значения погрешностей в; которые используем в качестве поправок к решению. Следующие приближения неизвестных имеют вид (1) (о) (о) (1) (о) (о) (1) (о) (О) Х1 = Х1 + е1 1 Х2 Х2 + во 1 ~ Хп — '1'и + и Таким же способом можно найти новые поправки к ре- (1) х' ' = шению е~ и следующие приближения переменных х( =- х,"~+ з1" и т. д.
Процесс продолжается до тех пор, пока все очередные значения погрешностей (поправок) е; не станут достаточно малыми. Рассмотренный процесс уточнения решения представляет фактически итерационный метод решения системы лн11ейных уравнений. При этом заметим, что для нахождения очередного приближения, т. е. на каждой итерации, решаются системы уравнений вида (4.24) с одной и той же матрицей, являющейся матрицей исходной системы (4.21), при разных правых частях. Это позволяет строить экономические алгоритмы. Например, при исполь- 5 3. итеРАционные методы зовании метода Гаусса сокращается объем вычислений на этапе прямого хода. Решение систем уравнений с помощью рассмотренного метода, а также при использовании других итерационных методов сводится к следующему (рис, 19), Вводятся исходные данные, например коэффициенты уравнений и Рис.
19. Решение системы уравнений методом итераций допустимое значение погрешности. Необходимо также задать начальные приближения значений неизвестных. Они либо вводятся в ЗВМ, либо вычисляются каким-либо способом (в частности, путем решения системы уравнений с помощью прямого метода). Затем организуется циклический вычислительный процесс, каждый цикл которого представляет собой одну итерацию.
В результате каждой итерации получаются новые значения неизвестных. При малом (с заданной допустимой погрешностью) изменении этих значений на двух последовательных итерациях процесс прекращается, и происходит вывод значений неизвестных, полученных на последней итерации. Заметим, что в этой схеме пе предусмотрен случай отсутствия сходимости. Для предотвращения непроизво- 136 ГЛ. 1. СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕППЙ а„х,+а„х,+а„х,= Ь„ аг1Х1 + аггХг + агзХг = Ьг а31х1+ аггхг + аггхг Ьг' (4.25) Предположим, что диагональные элементы а„, а„, а„отличны от пуля (в противном случае можно переставить уравнепия). Выразим неизвестные х„х, и х, соответственно из первого, второго и третьего уравнений системы (4.25): 1 (Ь1 а12хг а13хо) 11 1 = — (Ь 2 — а 1х1 — а 23х 3), 22 1 3 ~ ( 3 31 1 32 2)' 33 (4.
26) (4.27) (4. 28) Зададим некоторые начальные (нулевые) приблпже(о) (о) (о) иия значении неизвестных; х, = х,, хг = х,, х3 = х, Подставляя эти значения в правую часть выражения (4.26), получаем новое (первое) приближение для х,; и) 1 к (о) (о)) 11 Используя это значение для х, и приближение х3 для ,(о) х„находим из (4.27) первое приближение для х,: Х2 = — 1Ь2 — а21х1 — а23Х3 ), (1) 1 (1) (о) 22 И наконец, используя вычисленные значения х, =х,', (1) х2=х3'3 находим с помощью выражения (4.28) первое (1) дительпых затрат машинного времени в алгоритм вводят счетчик числа итераций и при достижении им некоторого заданного значения счет прекращают.
Такой элемент будет в дальнейп)ем введен в блок-схему. 2. Метод Гаусса — Зейделя. Одним из самых распространенных итерационных методов, отличающийся простотой и легкостью программирования, является л(етод Гаусса — Зейделл. Проиллюстрируем сначала этот метод на примере решения системы з 3. ИТЕРАЦИОННЫЕ МЕТОДЫ 137 приближение для х,: (д) 1 /е (ц (1) 1 хз ~~з аздхд азз 3 )' зз На этом заканчивается первая итерация решения си- стемы (4.26) — (4,28) . Используя теперь значения хд, (!) (д) (д) хз, х,, можно таким же способом провести вторую ите- рацию, в результате которой будут найдены вторые прпдз) (з),(з) ближения к решению: х, = хд, х, = х,, х,= хз и т. д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
