Буслов, Яковлев - Введение в численный анализ (947494), страница 12
Текст из файла (страница 12)
Норма оператора А определяется стандартно 'О АхО Яо 'ОхО Обозначим у = Ах и введем число т по правилу т=пш1 =п1ш, = (шах ) = ОА О 'ОАхО 'ОуО ? ОА-'у()~-' йо )(хО гйо ))А 'у)( (, эхо ((у)! ) Величина С(А) = зо = 'ОАО ° 'ОА ~О называется числом обусловленности. Очевидно Ц С(А) > 1; 2) С(аА) = С(А); «Ьн~ 3) если А — диагональная, то С(А) =,„;.„„(Для какой нормы? или для всех вышеприведенных?) Чем меньше число обусловленности С(А), тем лучше обусловленна система.
Действительно, пусть тзЬ вЂ” вариация правой части, а йх — соответствующее изменение решения. Тогда справедошво следующее неравеисово 'ОстхО 'О?хЬО 'Ох'О 'ОЬ'О Доказательство. Имеем: Ах = Ь, А(х + йх) = Ь + ЬЬ, Айх = лЬ. Так как 'ОА?тхО 'О?тЬО (),йхО !)ЬхО то ))ЬхО < — '((ЬЬО.
Аналогично, поскольку Ах = Ь, то ОЬО < ИОхр. Объединяя два неравенства, окончательно получаем ))Ьх'О М 'О?хЬ'О 'ОхО тп О'Ь'О' 5.2.2 Метод Гаусса Один из самых распространенных прямых методов решения систем линейных уравнений Ах = Ь 60 ап а!г . а!м Х1 ь, Ь, аг1 агг агм ам! амг амм является метод Гаусса. Вначале исходная система приводится к верхнетреугольному виду. Это достигается следующей последовательностью преобразований (прямой ход метода Гаусса). Будем считать для удобства, чг'о элементы а(1 исходной матрица! и компоненты вектора Ь, есть соответственно элементы а, первого шага преобразованной матрицы ОО А! и преобразованного вектора Ь1: А = А1, Ь = Ь1. Далее, на втором шаге прибавим к второй строке первую, умноженную на — -'2'- = сш . Аналогично поступим со всеми оставшимися строками, те прибавим к каждой 1;ой строке ап ! = 2, 3,..., Х, первую, умноженную на коэффициент,! = — -"'-'-.
При этом соответственно измен!ггся и вектор Ь1. Таким 411 ' образом 2 шаг) Имеем систему уравнений Агх = Ьг а(~ а(! П !2 (21 О агг Ь, Ь(21 2 а,, Оо агм (21 (2! О амг амгм хм Ь(21 гдеа(~=а)'!+с, а(, Ь(!=Ь(г+с Ь((, !'>2. (г1 3 шаг) Прибавим к новой третьей строке новую вторую, умноженную на сз = — (гп То 422 же самое сделаем с (21 остальными строками 4, о,..., А(, т.е. прибавим к каждой 1-ой строке вторую умноженную на с,г — — — 4гы, ! > 2. При гг этом получим систему Азх = Ьз ап а(1) а12 Р! Х1 О О О о о а а (з! (зг хм ЬР) ()4 -(- 1)ый !паг) здесь а( ~ ! = а( ! -(- си а(! 1, ь( ~ ' = ь( ! ~- с(з ь( 1, где сз = — (ззу, 1,, у > !4. Поступая так и далее иа (Х вЂ” 1)-ом шаге получаем верхнетреугольиую систему; О О О а 4 ОО О О О О Ь'„' (и) амм При этом мы также получили матрицу С переводных коэффициентов, имеюшую вид: О О О О О О О О О см сз1 сзг О О О см с42 с42 О О см! см смз смм-! О (!! а,з (2! азз (З1 а (11 0! ап !'ш а!з (21 (21 О агг агз О 0 азз (з) (О а!м Ьо а г„ (зг азм (1! а!м (2! а.
(3) азм (4! азм Ь, Ь(ю Ь(з! з д( ~ 1 Ь(2) Ь(з) з Ь(41 хн =, хь = (Хь — ~~~ (Хыхс), )с = Лг, ХХ вЂ” 1, ..., 1 Хне 1 ~ =ь -~-с Заметим, что при прямом ходе метода Гаусса может возникнуть ситуация, когда происходит деление на нуль, да и вообще желательно не делить на малое число, чтобы не накапливалась ошибка. Поэтому метод Гаусса обычно проводят с частичным выбором главного элемсн ц, то есть после каждого шага (пусть это был 1с-й шаг) переставляют строки с номерами х, Л+ 1,..., Л1 таким образом, чтобы на месте И оказался элемент а ы наиболыпий из всех в )с-ом столбце по при т > и (при этом, естественно, переставляются и компоненты вектора Ь). Можно для максимальной точности переставлять также и столбцы преобразуемой матрицы, чтобы на месте ЛЛ оказался максимальный элемент из всех с индексами больше либо равными (с.
Эта процедура называется методом Гаусса с выбором главного элемента. Она несколько повышает точность по сравнению с частиным выбором главного элемента, но весьма неудобна, в том числе и зщя программирования, поскольку при перестановке строк компоненты искомого вектора х переставлять не надо, тогда как при перестановке столбцов надо переставлять и соответствующие компоненты вектора х. Опишем обратный ход метода Гаусса в несколько иной форме (треугольное разложение).
Введем матрицы Мь по правилу 1 О . О . О О 1 О О О О 1 .. О О О ° ° сетьь ° О О О сс.д,ь О О О сн,ь .. 1 тогда на каждом шаге метода Гаусса получается некоторая промежуточная матрица Асзо — — МсМь ю .. М1А, и вектор Хьег = Мс Мс 1... М1Ь . Нетрудно видегтч что н — ! и — 1 Х.г = Я ЛХ,А, Х = Я ЛХ,Ь; (Хх = Х, бес П = П К, = бес А . Вопрос, Почему с1ес П = с1ес А? Ещш производить также выбор главных элементов, то необходимо использовать оператор Р перестановки индексов 1 и т, матричные элементы которого равны: р„= О, 1,Х Р 1,т; р, = р, = О, 1 ~ 1; рн = ро = О, 1 ~ т; р ~ = р~ = 1 .
При применении оператора перестановки индексов к матрице слева, меняются местами строки матрицы и компоненты свободного вектора (РАх = РЬ), ессчн же его применить справа к матрице, то меняются местами ее столбцы и коьшонеиты решения (А РР х = Ь). 5.2.3 к -К разложение Для решения задачи Ах = Ь несколько модифицируем ее. Именно введем Лс х (Л1+ Ц матрицу Решение полученной треугольной системы Пх = Х (1Х = Ал, Х = Ьн), как легко видеть, имеет вид (обратный ход метода Гаусса) ь, А ь, и вектор Х = (хь хз,..., хл, — 1) размерности (зУ+ 1), тогда исходная задача эквивалентна следующей г СХ = О Представим С в виде С = ЬВ, где Е нижнетреугольная ?У х зУ матрица 1и О О ?ш 4з О Ь= 1из 1ззз ' ' ' ?ям а  — зУ х (?У + 1)-матрнца вида 1 тзз тзз тьч тз,л-зз О 1 тм тзл тз,лэз О О 1 .
тзи тзлэз О О О ° 1 тл.лез Как находить матрицы Л и В? 1-й шаг) а) Умножим юзждую строку матрицы Х на первый столбец матрицы В, откуда Вз = с,|. Таким образом мы определили первый столбец матрицы В б) Умножнм первую строку Ь на каждый столбец В, откуда тз, = сь/?п, то есть определена первая строка 2-й шаг) а) Умножим каждую строку Е (иачнная со второй) на каждый столбец В и определим второй столбец Гх 1ш = с,з — 1.зтш.
б) Умножая вторую строку Ь на каждый столбец В определяем вторую строку В: тз; = (сг, — 1шть)/1хь т-й шаг) Пусть известны первые т — 1 столбец Ь и ш — 1 строка В, тогда при? > т ш — 1 сиз ~ 1зззтз~ э=1 1, = с, — ~ 1;зтз,„, т Теперь заметим, что вовсе нет необходимости решать задачу СХ = О, а достаточно решить систему ВХ = О. Действительно, ранг матрицы В равен зУ, таким образом исходная матрица А и Ь вырождены или невырождены одновременно. Компоненты х, находим последовательно, начиная с Л'-ой: Л хм = тл,л+з, х, з = томаз — ~ т зхз з=зез Вычисления по изложенному методу требуют в два раза меньший объем памяти, чем по методу Гаусса.
5.2.4 Метод прогонки Пусть А — трехдиагональная матрица, которую мы представим в виде: -ь, о о о " о о — аг сг — Ьг ΠΠΠΠΠ— аз сз — Ьз ΠΠΠΠΠΠΠΠ— агу ск Знак — перед Ь,1с, поставлен для удобства.
Для решения задачи АЬ = з в этом случае применяется метод прозаики. Положим аг = Ьн = О, тогда трехдиагональная система может быть записана в виде — гаь + Ььсь — ЬьэгЬь = зь, к = 1, 2, ..., 2У Рассмотрим эту систему подробнее. Выразим из первого уравнения гс через Ь1 ь С1 С1 11сг — сгьг = зг Теперь из второго уравнения выразим 12 через 12 . — 11аг + Фгсг — ьзь = зг, или Зг + З1 ь! Ьггз — ~ — + — Ьг) аг + сгсг — ЬзЬг = зг ~ 12 = + '1С1 С1 ) сг — -,1-аг ь сг — —,1-аг ь 21 Аналогично Ьь = оььь-ьс+ дь зь+дь гаь 1)ь = сь — пь гаь Убедимся в справедливости этого представления по индукции. Действительно ол = ~~-, )21 = -'„.х, таким образом база 1' -1 индукции верна. Теперь осуществим собственно индукционный переход.
Пусть Ьь = аьььег+ дь, тогда — аьэггь + сь.ь11ь.ы — Ьь.ь1зсэг = зьт1 — аьтс(аььь.ы + сггьс) + сь ьгсьэг — Ьь.ьгсь.ьг = ззег откуда Ьь.ьгььэг зьэг + дьаьэг ЬЭ1 — + аььг Ьььг+ бь.н сье, — аьаьэг сьзг — аьаьес аь = — — '-— ь ы — гз-1аь а — 1. ь 1 зьэзь-121 ггь = Ь вЂ” 1-1 Ь После того как определены коэффициенты аь и дь начинается обратный ход прогонки — собственно определение КампОНЕ1ГГ ГЬ . Имеем то есть индукционный переход также имеет место. Рассмотрим теперь каким образом применяется метод прогонки. На первом этапе (прямой ход прогонки) мы определяем коэффициенты аь, бь через известные нам элементы матрицы А (Ьь, сь, аь), заданые значения зь и предыдущие пь 1, дь при этом ам = О, тк Ьл =О, а ал = л .
Таким образом ь„ ои — ан — гон ел=Фи ( ) Сь = а,сг„., +(дг ( ) . Утверждение (Достаточное условие разрешимости прогонки): Пусть )сь! > )Ьь)+ )аь), Ь = 1, ..., 1У, тогда с)ес А ф О. Доказательство. Необходимо убедиться, что знаменатель в формулах прямого хода не обращается в нуль. Для этого достаточно убедиться в том, что ~аг ~ < 1. Ведь если это так, то ~сг — аг саь) > ~сг~ — )аь сОаг! > (сг) — ~аг~ > ~Ьг~ > О и не происходит деления на нуль. Имеем М1= )Ьь! (Ьг! < — =1 )сг — аг гаг( (Ьь) 1а ~=! — !<1 Ьс сс Метод итераций для решения линейных систем Система линейных уравнений Ах = Ь апхг = Ь;, г = 1,2,...,Х, Е имеет единственное решение> т.е.
что с1ег А ~ О. Представим матрицу А в виде А = В+ Р, где Р = с11ая(асс, ..., алл1 . Предположим, что с1еСР ф О, что равносильно тому, что а„эг О, г = 1, ..., Х (если исходно этапе так, то перестановкой строки столбцов этого всегда можно добиться при с)ее А р О ). Тогда (Ц переписывается в виде Рх = Ь вЂ” Вх, или х=Р 'Ь вЂ” Р 'Вх Предложим следующую итерационную процедуру х'~' = Р 'Ь вЂ” Р 'Вх' х — произвольный начальный вектор.
В развернутой форме о х,' =а„Ь, — а„гг абх,', г =1,2,...Л г = иг а Обозначим Р Ь = и, Р В = Т, тогда итерационный процесс принимает вид — 1 — с х~~ = и — Тх (2) Теорема1. Процесс (й) сходится, длл любого начального вектора, если ОР '(А — Р)~~ = 'ОТО' < 1 Доказательство. Для доказательства достаточно заметить, что отображение х э и — Тх является сжатием.
Таким образом последовательность х' имеет предел. Пусть х* = 1пп х", тогда х" = и — Тх*, или возвращаясь к исходной формулировке Ах* = Ь . Итак для сходимости изложенного метода, называемого методом простых итераций, необходимо чтобы г=1 может быть решена не только прямыми методами, но также и итерационными. Разумеется мы предполагаем, что система 5.2.5 Метод Зейделя Модифицируем метод простых итераций, координатную форму которого, в частности, можно записать в виде з<~ з>~ Заметим, что если последовательно вычислять компоненты (л+ 1)-го приближения х"э начиная с первой г',т, то к е -~-1 э1 моменту вычисления конкретной 1-ой компоненты х,'т', координаты г',т', ..., г,'.э,' уже определены и их можно было бы использовать для определения более точного последующего приближения х'+' .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
