Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 87
Текст из файла (страница 87)
Таким образом, лля релаксационности процесса на данном шаге нужно, чтобы ~ см / с, / а;. !. Этого можно добиться, только если а,~+ (). Легко проверить, что ' 1 с;~ = а;) (са — аг) + (ау; — ам) са == а;~ соз 20+ — (а)) — ан) мп 20 = = аы з(п(20 — 20 ), 538 итвгхционныз методы для вешания полной пговлзмы (гл. тлп где скы= аг а;,+ — (ац — ан)а, 10;20з=' . Угол бе опре- ан — аау ' делен с точностью до целого кратного — . Мы будем считать, 2 ' что — 4 с. 0з ( 4 . При таком условии выбора Оз и $ 'У+4 1 На рнс. 12 приведен график с;.
как функции от О, в предположении а; ) О и 0з) О, Ясно, что при других знаках а;. и 0з соответствующие графики для с; будут иметь такой же вид с точностью Рнс. 12. до симметрии относительно оси абсцисс (при изменении знака а .) гу или относительно оси ординат (при изменении знака 0е). Из графиков можно заключить, что значения О, обеспечивающие неравенство Р (с) ( Р (А), заполняют четыре интервала на промежутке ( — п, и), каждый из которых приныкает одним из концов ч т. к точкам О, —, — — ', — к (или +и). В дальнейшем мы будем считать, что угол вращения 0 на каждом шагу якобиева процесса берется из промежутка (О, 20,) нли (20з, О), примыкающего к точке О, так что 0=лйз, где О .~у(2 и (О„)( —.
Наибольшее понижение величины Р(4) за один шаг получится при сО=О, что будет обеспечено при 0 = 0,. По аналогии с релак.- сационнымн процессами для решения систем линейных уравнений мы будем называть якобиены процессы, в которых на каждом шагу 0 = Оз, процессами с подной релаксацией, Аналогично процессы. в которых О С и ( 1. мы будем называть процессами с нижней релаксацией, процессы, в которь1х ! ( и ( 2, — процессами с верхней релаксацией. Выбор пар индексов (тп у',) (!з, /а)...,, (га, уа) для поспелова" тельных шагов процесса можно осуществить априорно или с упра. влением по ходу процесса.
Наиболее естественным для априорного выбора является циклическое чередование пар, занумерованных теи или другим способом. $ 81! пеоцвссы, основлнные нл пеимвнении ввлщвний 539 1г( 1(леи) 1г ( ~<а>) 2( (л> )г стороны, 1'(А! >) < п(п — !)(а(„>,„), откуда (а( 11„)'»> /г (А1~>). Следовательно, 1г(А<а+И) (1г(А>л>) (1 п(п — 1)/' С другой 1 >~ —— п(п — Ц н потому 1 (А ) ( 1 (А)(! — ) Таким образом, 1(Ани) -ь О при й -> со. что доказывает сходимость процесса Якоби.
Дадим расчетные формулы одного шага метода, обозначая снова исходную матрицу шага через А и полагая С = Т',„.АТ, !<ак уже сказано выше, пара (1,./) выбирается так, чтобы а;. был наибольшим по модулю элементном матрицы А. Далее сь, = ага при 1+1, /гчь/, 1ф1, 1+/ сл; — — сев —— са„, + заь/ (1) сл =с.л — — — гам+сна при /г +С й+/. Наконец, сн — — сгам+ 2сза;, + ага;1 с11 — — л-"ам — ' 2сза;1+ сга.1 сн = (с' — аг) аг/+ сз (а.> — ан) = О.
(2) Числа с и з определяются по формулам с=соа0, а=з!п0, (8) где 1820=, !О! < —. ам — а/1 ' (4) Перейдем к рассмотрению нескольких исследованных в настоящее время якобиевых процессов. 1. Классический метод Якоби. Матрица вращения ТО выбирается на каждом шаге так,. чтобы элемент 1-й строки и /'-го столбца преобразованной матрицы стал нулем.
При этом пары индексов (ю', /) выбираются на каждом шаге так, чтобы аннулировался наибольший по абсолютной величине недиагональный элемент матрицы, полученной в результате предыдущего шага процесса. Таким обрззом, метод Якоби является методом полной релаксации с управлением. Легко доказывается сходимость метода. Действительно, пусть А — матрица. полученная на и-м шагу процесса, аг;а ее наибольы> >л> ший по модулю недиагональный элемент. Тогда 540 итеРАциОнные метОды для Решении пОлнОЙ пРОБлемы (гл. мп Формулы (3) и (4) можно заменить на / 1( ~ам — ау 1т а=з1ип [ай(ан — ау)1 а — 2~1 — и У ), (5) где ГГ = ~/(а . — а ..)Я -+ 4аз Формулы (2) можно заменить на ан — ауд сн= 2 +з1ПП(ан — ау )— игг+ а ~ — з!Нп(ан — а у)— с13 — — с т = О. Построение матрицы С, после того как числа с, г вычислены можно осуществлять и непосредственно по формулам $ 51.
Если матрица не имеет кратных собственных значений, то, аннулируя внедиагональные элементы с точностью до а, мы получим, что диагональные элементы приблизятся к собственным значениям уже с точностью до е'. Действительно, если недиагональные элементы симметричной матрицы пы пге ° Н1 ааг ааа ...
аьв "ва овв л у г ю г .г г (6) верная с точностью до малых 3-го порядка, В самом деле, пусть аы — — еам, где в в малое число. Положим 1, = ан -+ йе'-'. Тогда для определения и получим уравнение — /гв' ецга еам аеа — ам — ле~ еягв а„в — ам — вез Ецв! Еввз являются малыми числами, то для ее собственных значений снраведлнва приближенная формула пвоцкссы, основлннык нл пвимкнкнии вглшкний 541 9 81) Вынесем е из первой строки и первого столбца определителя и заме- ним е нулем в получившемся уравнении.
Получим — )в а„... а,п ав, а„— а„... 0 апь 0 ... апп — аи откуда а "и" и + пи*и + ! пвпппь ан — авв аи — авв аи апп с точностью до малых порялка е. Следовательно, + ав ам + аиам + + авпапв + О( в) аи — аж аи — авв аи — "пп ь ь Аналогично ав )„.=,и ! ~~) " +О("). ув вишь Огрубляя последнюю формулу, получим ).ь = ан+ О (ев). Применим метод Якоби для определения собственных значений матрицы (4) 9 51. Первый шаг процесса заключается в преобразовании вращением при помощи матрицы Ты.
Вычисляя по формулам (4), получим с = з = 0.70710678. Лалее 1.66 0.608!1183 0.53740115 0 0.60811183 1 0.32 0.0!414214 0.53740115 0.32 1 — 0.22627417 0 0.014!4214 — 0.22627417 0.34 Т'„А Т„= Следующие шаги требуют преобразований матрицами Ти, Ти, Т„. Ти Ти Тв, Тем В результате получилась матрица 2.3227487 — 0.00048637 0.00001483 0.00004994 — 0.00048637 0.63828393 0 0 00004930 0.00001483 . 0 0.79670201 0.00161630 0,00004994 0.00004930 0.0016!630 0.24226544 642 итяглционныв матовы для ввшения полной пговлвмы [гл.
лп Ее недиагональные элементы уже настолько малы, что для определения собственных значений можно применить формулу (6). Вычисляя, получим Л, = 2.3227487 -+ 0.00000014 = 2.32274884 Л, =0.63828393 †.00000014 = 0.63828379 »з — — 0.79670201 + 0.00000471 = 0.79670672 ), = 0.24226544 — 0.00000471 = 0.24226073. Результаты получились верными уже с точностью до 4 ° 10 для всех сабе~венных значений. Нетрудно показать, что з случае отсутствия кратных собственных значений у исходной матрицы, метод Якоби обладает квадратичной сходнмостью. Допустим, что процесс проведен настолько дзлеко, что все недиагональные элементы матрицы стали по модулю меньше малого числа е.
Тогда, как мы видели выше, диагональные элементы приблизятся к собственным значениям с точностью до за. Поэтому на каждом шагу процесса Якоби угол поворота 6 будет иметь поря2а9 док з, ибо (я 26 = , числитель имеет порядок е, а знаменаигг — идГ ' тель, равный Л,— »1+0(аа), ограничен снизу.
Все меняющиеся на этом шагу недиагональные элементы, кроме а; ч изменятся на величину порядка е'. Действительно, сл; = сгя — — аы соя 6 + аь~ ейп 6, откуда сга — аы — — ага (соз 0 —. 1) +а„у з(п 6 = 0 (аа). Аналогично с„,— а„, = 0(ае).
В частности. элемент, аннулированный на предыдущем шаге. станет, самое большее, величиной порядка еа. Поэтому после, самое п (и — 1) большее, шагов процесса, все внедиагональные элементы 2 станут величинами порядка е'. Это и доказывает квадратичную сходимость процесса. Подсчет констант в приведенных оценках осуществлен в работе Хенрисн [1[, Скажем несколько слов о нахождении собственных векторов.
Пусть процесс доведен до того, что матрица 4 =(ПТ у ~ 4~П7''„,г ~ э 81! пгоцвссы,.основанные нь пгнмвнзнии ввашений 543 оказалась практически диагональной. Тогда столбцы матрицы И Т~ « и будут собственными векторами исходной матрицы А. В случае, если собственные' значения матрицы А попарно различны и внедиагональные элементы матрицы аннулированы с точностью до малого числа е, легко дать прием, позволяющий вычислять компоненты собственных векторов и; с точностью до величины е'.
Именно, и,=Дтг, !гп где «ы «~-~~ ! «г+~г «1« 1= «и «и «ч «1-г '-г «и «~ .г г -г «и «««) Здесь «; — суть элементы матрицы А, на которой мы остановили сю процесс. В качестве примера определим собственный вектор матрицы, рассмотренной выше в связи с определением собственных значений, принадлежащий наименьшему собственному значению. Имеем а„ вЂ = — 2.08048326. ам †««а = — 0.39601849, 'Ъ вЂ” и«« = — 0 55445657, ~ак что Ъ', = ( — 0.00002400, — 0.00012449, — 0.00291521, !)'.
Д,злее находим по формулам (8) 9 51 последовательно векторы Т««Ъ 4, Та«та«Ъ ц Т1зта«тю~lь, тытытыт„тыт„т„т,,!г, = и,, располагая нх компоненты последовательно в графах ! — !ч' табл. Ч!!!. 7. В графах Ч и Ч! приведены соответствующие коэффициенты с н з. В последней строке приведен собственный вектор и,, нормированный к единичной первой компоненте. Классический метод Якоби на каждом шагу процесса требует выбора наибольшего внедиагонального элемента.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
