Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 71
Текст из файла (страница 71)
Днучленные формулы метода минимальных итераций тг биортогонального алгорифма Системы векторов ро...., р„, и,у, ..., ~у„,, тесно связаны друг с другом, и их олновременное вычисление может быть осуществлено по формулам более простым, чем трехчленные формулы, определяющие каждую из этих систем в отдельности. Именно, справедлива следующая Теорема 67,1. Ес,ги А — положительно-определенная матрица, векторы Х, АХ, ..., А" Х линейно-независимы, векторы ро,..., р„, получены из них процессом ортогонализации, а векторы ао, ..., ао, процессом А-ортогонализиции, то между векторами построенных систем имеются следующие двучленные соотношения Ро= Чо Ргч г = А7г рерг гу;„г = — р;+д — а; ь,гуо где (ри Авд (аь Авд (УЧ Р') (Рг Рг) (рг+ь рг+д (рг+г рг+т) г+' (рь АВ) (Вг Авд (2) р' (Рг+т — Ааь рд (АВ Рг) (Рг Рг) (Рь Рд ибо (р; „,, р;) = — О. Доказательство.
Равенство ро=гуо непосредственно следует из построения. Обозначим через Р, подпространство, натянутое на векторы Х, АХ, ..., АгХ, через Р; множество векторов А'Х+У. где У~-Рг,. Векторы ро, ..., Ро так же как и векторы ~уо, .... ~уг образуют базисы подпространства Ро причем р, ~ Рд дг ~ Р,. Далее, если Л ~ Ро то АЕ ~ Рг„.о в частности, Арг ~ Р; „и Ад; ~ Р; „,. Рассмотрим вектор р,+, — А(у;. Вектор Ааг ортогонален к векторам ао, ..., (у; и, следовательно, ко всем векторам подпространства Рг,, в частности, к векторам р„ ..., р;,. Вектор р;,, тоже ортогонален к ро, ..., р, , Следовательно, и вектор р,„, †А ортогонален к Ро ° Рг н С другой стороны, вектор р;+, — Ад;, как разность двух векторов из множества Речи принадлежит подпространству Р; Поэтому реь, — А(уг = — р;ро где рг некоторое число.
Ясно, что 428 [гл. Тл МЕТОД МИНИМАЛЬНЫХ ИТЕРАЦИЙ Но Ад; — р;,г~РО д; — р;~Рг о так что ()тг,о Ад;)=(рг„,, рг г), (Адг дг)=(Ади Р1). Следовательно, а Ой+г рг+1) (рА~1 р~~-д) . (дг Адг) (дь Адг) (ри Адг) ' Р' (йь рг) Теорема доказана. Замечание 1. Если А симметричная, но не положительно-опре- деленная матрица, то теорема остается верной при условии, что про- цесс А-ортогонализации не имеет тупикового окончания. Залгечание 2.
Полиномы пг(1) и дг(1) также связаны, очевидно, двучленными соотношениями Р„,(г) =гд,(1) — р;р;(() (3) дг+1(1) =р$ г(г) аг. 1дг(г). Легко устанавливаются связи между коэффициентами двучленных формул р; и аг и коэффициентами трехчленных формул и, и рэ или Тг и а,. Именно, по= ро (1=1, 2, ..., л — 1) (1 = 1, 2, ..., п — 1) (4) а,=р,+аг ~1 —— Р;,аг '(г=р;+а,„(1=О, 1, ..., л — Н а; = рга; (1 =- 1.
2, ..., и — 1), Действительно, в силу двучленных соотношений (1), имеем Рг+г = Адг ргРг Ад; = Арг — а;Ад; Рг =Ада-т рг-грэ — г Исключая из этих соотношений Ад; и Адг о получим пг+г —— Арг — а;(р;+р; грг,) — р;р„= =Апэ — (а;+р;)рг — а;р; грэ .= Арг — игр, — 'ргрг (6) Теперь рассмотрим вектор дг+,— р,~о Этот вектор. принадлежит подпространству Ро Далее, вектор р; Р, ортогонален ко всем векторам подпространства Ро в частности, к векторам Ада, ..., Ад, так что вектор р,э, А-ортогонален к векторам да, ..., де ы Вектор же д;„„А-ортогонален к векторам да, ..., д;, по построению. Следовательно, вектоР дг~, — Рг+, тоже А-оРтогонален к векторам да, ..., дг н ПоэтомУ д;„,— Р;„Р,= — а;+,до где а;, некотоРое число.
Очевидно. что (дг+, — рг+м Адг) (ргть Адг) (Ади д ) (Ад, д;) 429 4 67) дяячлвнные еовмхлы Отсюда, в силу линейной независимости векторов р; и р; о получим а;=а,+ра В,=за а,. Аналогично, искшочая р;, и р; из соотношений Ч;+1 — — р;„— а;,Ч; р;„, = АЧо — о,р; й Ра аоЧа-а получим Ч;, =-АЧ; — о,Ч, — ооагЧ;,— а,Ч; = = ЛЧ; — (Р;+ а;+,) Ч; — Р;а;Ч; АЧ3 ЪЧг йзЧ(-г откуда Т' = р'+ а' гг о;=р;ао + ~~а =ЯрА. 1 Лвучленные формулы сушествуют и для одновременного построения биортогональных и А-биортогональных систем, в случае, если оба процесса не вырожденные.
Именно, если Ро=Чо Ро=Чо то Раог = АЧо Рсра Рсоа = ' ( Ч1 Рьаа Чг,1 — Р;.,— а;,Чг Ч;, =Р; — аг„йь где (Ро А Чг) (Ро АЧг) (Ро Р~) (Рь РЧ) (Рг+и Рьм) (Рс~| Ргч-г) (7) а;„1— (ро А'Чг) (рп АЧД Соотношения (4) и (5) по-прежнему сохраняются. Локазательство принципиально ничем не отличается от доказательства. проведенного выше. Выведенные соотношения в частности, что и-1 Дйо между коэффициентами показывают.
430 !гл, чг метод минимАльных итеглций Одновременное вычисление биортого Ро АЧо А'Чо Ро Чо 0.26985! 0.288043 ~ — 5.363684 ! — 14.137401, ! — 7.503621 — 7.503621 — 7.503621 — 7,503621 ' !Ч ( 7.503621 — 0.23490436 3.2259404 — 49.43280 0.3717982 †1.93761 — 0,3385964 — 0.6764826 166.93761 — 84.06708 2.12. 10 в — 1.24 ° 10 0.31 ° 10 0,66 ° 1О-в 1.122259 — 133.49987 0 0.0? ° 10" о 0 0.07 ° 10 о — 221.18891 — 22!.18892 36.894860 Зб.
894860 36.894859 !.32210!? ( !Ч ! — 5.9951147 ~ 8.6346552 16.298936 — 16.298936 3.7527932 Ч 1 20.963280 99.233549 0 1 1 0 2.6926058 0 — 1.0979091 — 1.1323868 11,594561 9.852133 — 9А80335 4.179904 1 22.546044 111.48181 1.870086 — 11.811654 4.308033 0.336964 — 7.503621 — 7,258787 — 17.688366 0 6.934482 11.8?6143 431 9 671 двхчлвнныв еовмглы Таблица Ы.
76 нальных и А-биортогональных систем А'д, Аде 029 1О-е! 001 10-е ( 159126943 110411242 !.7626333 1.7626333 1.7626333 — 23.3 ! 0394 — 23.310394 — 23.310394 — 23.310394 — 1.5827643 ! — 13.224755 ~ 1-"- ' 1 7.738525 1 7.503621 Абе Ре — 5,8109067 — 48.220650 — 0.4915550 1430.8088 0.8000499 -1430.8088 5.9817370 !272.5854 ОЗ2. !О п,оз. !о-' 2 86 1О-в ~ †2.43424 6044.4321 6044А32! †2.43426 †2.43424 — 20 669372 1.870086 — 4.308033 4.308033 0,269851 2.332948 — 69.2236\ 9 69.223619 — 61.568654 0 478.10-е — 0.84 1О 1 28.541159 237.15908 594.91651 0.336964 0 0.244834 0.288043 — 1.5458854 0 0.3523910 5.0873542 0 1.03 ° !О в 2,48 ° 10 1. 8700860 — 4.0731286 4 3080330 0.2698510 — 12.996241 — 82.249! 41 81.757586 — 67.094912 — 586. 10 е 61 46. 1О-в 643.
10 в 1 27.219057 207.35092 447.52622 0.33696400 0.23490436 0.47973836 0728804300 — 16.096774 73.271617 — 73.2716!7 0.18407987 — 1.7636605 0.00000001 — 4.3357788 — 4.9416849 — 0.00008 0.00006 — 0.00006 — 0.00001 1 , 47.888429 797.27875 5349.4555 ~ !2296.551 432 ИТЕРАЦИЙ [гл.
МЕТОР МИНИМАЛЪНМХ $ $ а 1 1 $$$$ 38 Я 8И $ 3 ф 78[О 1 о о 888 4868 о о б ММа О 1 О 8 8 8 8' о о о а о 1 1 ! О О О а о $9$$ о 8 о' о 1 ! $$$1 о о а ! 1 88$$ о о,о О ! ! М ! о о Ь о о О й( О йййЗ 'о'оо а аь й й й М М о о О О О О О О О О О. 1 1 о о Д С' о о 8 И Я о о 1 ! 1 о о о о 8 38 о о 8 о 1 о о 1 о о ййй ооб 1 1 о о ь ооо 1 1 о й Ж 8 а о а о 1 8 М $3 й 8 В $ О '1 3-$ о а 8 Н 1 $3 1 5 68] методы сопРяженных ЯАпРАВлений и их авшие свойства 433 Б табл. Ч!. 16 приведено одновременное вычисление биортогонального и А-биортогонального базисов для матрицы Леверье, в табл.
У!. 17 приведено одновременное вычисление ортогонального и А-ортогонального базисов для матрицы (4) й 51. 5 68. Методы сопряженных направлений н нх общие свойства Методами сопряженных направлений для решения систем линейных уравнений АХ= В (1) называются методы, в которых решение Х представляется в виде линейной комбинации векторов, ортогональных в некоторой метрике, так или иначе связанной с матрицей системы. Термин „сопряженные направления" происходит от того, что направления векторов, ортогональных в некоторой метрике Й сопряжены по отношению к поверхности второго порядка (ВХ, Х) =сопз!.
(2) Метод А-минимальных итераций, также как н методы А'А и АА'-мннимальных итераций являются методами сопряженных направлений. Каждый отдельный метод характеризуется выбором метрики и выбором исходной системы векторов, подвергающейся ортогоналивации. При построении системы й-ортогональных векторов часто используются формулы теоремы 11.20. Методы сопряженных направлений укладываются в следую|цую общую схему. Пусть В = СА — положительно-определеннзя матрица.
Пусть, ДаЛЕЕ, ПОСтРОЕНа СИСтЕМа И-ОРтОГОиаЛЬНЫХ ВЕКТОРОВ Ро ..., Ьо (ВЕК- торов В-сопряженных направлений). Ин|ем решение системы в виде Х=Хо+В~л„'| атзп (3) Здесь Х,— начальное приближение, выбираемое, вообще говоря, произвольно. Обычно берется Хо — О. Подстановка (3) в систему дает АВ:..', а|в| —— Р— АХо — |.о.
| | Умножая последнее равенство на С, получим й.~~ а| я| = Сго |-| 434 (ГЛ, Ч» МЕТОД МИНИМАЛЬИЫХ ИТЕРАЦИЯ откуда коэффициенты а» легко определяются. Именно, (Сго, в») (йе в (4) Решение (3) можно представить также в виде в Х = Х, + ~1~ а»Взо (5) »=1 Векторы Вз,, ..., Вз„, в свою очередь, ортогональны в метрике, определяемой матрицей й,= — В' 'йВ 1, которая, очевидно, положи- тельно определена. Действительно, (йВЕО Вз») =(Вй»Ввь ее) =(йвп з) =-0 (» тку).
В известных частных методах сопряженных направлений или й = А (А положительно-определенная), или й=А'А, или й=АА'. В первых двух случаях В=В и системы векторов е,, ..., Рв и Вз,, ..., Вв„ совпадают. В последнем случае й, = г и построение системы Ве,, ..., Вгв осушествляется проще, чем построение системы е,, ..., е„. При этом оказывается возможныи исключить векторы еп ..., е„из формул для решения системы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
