Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 52
Текст из файла (страница 52)
Схема (РП) содержит произведения чисел Р; н Р, на компоненты соответствующих векторов и получается из схемы (!); последняя строка осуществляет контроль например, ~, Р',,хт = а„. Схема (!Ч) содер- 1 жит множители . А, где вместо) последовательно взяты три вычиА~ — А ' сленных корня. Далее, нормирующие множители определяются из схемы (П) и двух аналогичных схем, служащих для вычисления двух других корней, Так как ~'(Х~) ) О, 307 эскллатовный метод ф 48! Второй этап окончен.
1П э т а п. Вычислив величины Ра и Р,', пинаем эскаваторное уравнение для матрицы А,: О.1 И43! 0.20372! 0.01820! 17.596207-+ Х+ — !7.397000 — к — 7.594378 — . + — 5 300!00 — 1 — 0 и вычисляем его корни: )ч = — — 17.863262, )э —.— — 17.152427 ),а = — 7.574044, >4 — — — — 5.298698 ~~.", >ч = — — 47.888431; Бр Ач = — 47.888430. г=! амадее вычисляем собственные векторы матрицы Ао нормируя их обычным образом: и собственные векторы матрицы А',: 308 ПОЛНАЯ Ннов!!ЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ (гл. !у Окончательным контролем вычисления является вычисление произведения двух соответствующих матриц, состоящих из компонент собственных векторов. Вместо единичной матрицы была получена матрица 1.000005 — 0.000004 0.000000 0.000002 — 0.000003 1.000004 — 0.000002 — 0.000003 — 0.000002 0.000000 0.999994 0.000000 — 0.000001 0.000000 0.000004 1.000006 Наконец, для сравнения представим эскалаторное уравнение в виде обычного полинома: 14+ 47 8884301!+ 797 27877!а+ 5349 45561+ 12296 550 0 а собственный вектор, принадлежащий )ч нормнруем так, чтобы его первая компонента была равна единице.
Это дает Х4.— — (1; 0.098820; 0.062183; 0.009741)'. Мы видим, что коэффициенты написанного уравнения совпадают с ланными Леверье с большей точностью, чем прн вычислении другими методами. Соотношения ортогональности также выполнены со значительной точностью. 9 49. Метод интерполяции Методы, приведенные нами в предыдущих параграфах. решали задачу приведения к полиномиальному виду векового уравнения.
Развитый в этом параграфе метод интерполяции применим к более общей зздаче, а именно к развертыванию определителя вида 7!! (1) Л» (1) Р (1) = ! УА!(1) . УАА(!) (7!Е(г) данный полином от г), в частности, к РазвеРтыванию хаРактеристнческого определителя А)(У) = ! А — ХВ ! н определителя !! А — В1(. где А и В данные матрицы. Сущность метода заключается в следующем.
Пусть известно, что Р(1) есть полином, степень которого не превосходит числа /г, Как известно, такой полипом вполне определяется своими значениями в г!+1-й точке и может быть восстановлен по таким значениям при помощи той или другой интерполяционной формулы. Поэтому для явного представления В(1) нужно вычислить значение м+ 1 численных определителей 309 э 491 МЕТОД ИНТЕРПОЛЯЦИИ ч~~ агР(О) (3) где Ь1Р(1) обозначает1-ю разность вычисленных значений полинома Р(У), определяемую по рекуррентной формуле Ь1Р(1) = 11 'Р(1+1) — Ь' 'Р(1). Положим т(г — Н ...
(т — 1+ 1) й Тогда формула (3) преобразуется к виду: Р(1).=.'.,","Ь'Р(0) ~ с„,й )= 1=0 тп / = Р(0)+ ~, (~~" см1~АР(0) 1Р1. т=-1 Чг=м (4) Эта формула носит название интерполяционной формулы А. А. Маркова. В работе Ш. Е. Микеладзе [11, в которой был описан интерполяционный метод раскрытия полиномиальных определителей, в качестве интерполяционной формулы выбрана формула (4).
Таблица коэффициентов интерполяционной формулы А. А. Маркова для лг (1(20 приведена в книге В. Н. Фаддеевой (11. При пользовании интерполяционной формулой целесообразно для контроля опорных значений определителя (1) вычислить еще хоть одно значение Р(1), именно, в нашем случае. Р(й+1), ибо дье1Р(0) должно быть равным нулю, а ЬвР(0) и ЬьР(1) равными между собой. Метод интерполяции требует большого числа действий. Так, для вычисления коэффициентов характеристического полинома при помощи интерполяционной формулы (4) требуется прежде всего вычислить (и+1) определителей и-го порядка.
Это потребует и+1 3 (и — 1)(из+и-+3) умножений и делений, где )ти )ч, ..., Хь некоторые числа, выбираемые, вообще говоря, проиавольно. Вычисление нужных определителей можно осуществить, например, по схеме, изложенной в $11. Лля построения полинома Р(1) по его значениям наиболее удобно пользоваться интерполяционной формулой Ньютонз, применимой для равноотстоящих абсписс )О Мы приводим формулу Ньютона для )ч = 1, 1 = О, .... А: ПОЛНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ !гл. ш 310 Если коэффициенты интерполяционной формулы взять из таблицы, то для получения коэффициентов характеристического полинома нужно еще произвести —,— умножение. п(п+ 1) о Таким образом, общее число нужных операций умножений и де- лений ( — 1)( -+ +3)+.
' + ) на много превышает число операций, нужных для вычисления тех же коэффициентов по методу А. М. Данилевского и по методу А. Н. Крылова. Кроме того, указанный метод не позволяет как-нибудь упростить задачу нзхождення собственных векторов матрицы, в то время как при вычислении по методам А.
М. Данилевского или А. Н, Крылова задача об определении собственных векторов матрацы сильно упрощается. Тем не менее, метод шжерполяции интересен как метод, дающий возможность решать более общие задачи. В качестве примера снова проведем вычисления для ма~рицы Деверье.
Опуская утомительное вычисление определителей, найдем, что ~ (О) = 12296.55, О(1) = 18492.17, <Р(2) = 26688.68 9(3) ='36894.41, сР(4) = 49771.69. Далее, составим таблицу разностей: зз да 12296.55 18492.17 26583.68 36894.41 49771.69 6195.62 1895.89 8091.51 323,33 2219.82 2566.55 10310.73 12877.28 347.33 (Отметим, что в случае вычисления коэффициентов характеристического полннома вычисление лишних знзчений 9(1) для контроля можно не производить, так как надежным контролем в этом с.чучае является равенство ЬА~7(0) = ( — 1)" и!).
Наконец, вычисляем коэффициенты характеристического полинома, располагая вычисления по схеме: 9 49] 311 мвтод интвгполяции дгт (о) сы 6195.62 1895.89 323.33 24.00 1.0000 0000 0.5000 0000 — 0.5000 0000 — 0.5000 0000 0.3333 3333 0.4583 3333 — 072500 0000 0.1666 6667 — 0.2500 0000 0.0416 6667 79?.280 5349.45 47.8883 Коэффициент р4= р(0) = 12296.55. Метод интерполяции првменим всегда; в частности, случай, когда характеристический полипом имеет кратные корни, ничем не выделяется среди других случаев. Если вместо чисел О, ..., (з взять в качестве узлов интерполяции числа 71= а+л1, то формула (4) видоизменится следующим образом: л 7 ь Р (1) = Р (а) + ~х'.~ ~ ~ с;(г Ьгв (а) (à — и) 1и=г а иа (5) Иногда может быть целесообразно в качестве интерполяционных абсцисс брать неравноотстоящие числа.
В этом случае можно пользоваться общей интерполяционной формулой Ньютона. Однако в случае неравноотстоящих абсцисс удобнее строить нужный полипом методом неопределенных коэффициентов. Именно, Р (1) = леть+ а,в-г+ ... + аы Тогда для определения чисел а, 7' = О, ..., 74, мы получим систему алгебраических уравнений Г()ч)=па);+лгЛ + . +а, которую можно решить каким-либо из изложенных методов. Метод интерполяции удобно применять, в частности, к раскрытию определителя /А — ВС! в случае, если матрица В имеет малый определитель. Если же определитель В не является малым числом, то определение коэффициентов искомого полинома лучше производить посредством преобразования ~Л вЂ” В1~=~В~ 1ЛВ-' — 7В~. Матрица АВ ' может быть найдена по методу исключения (9 22). Интерполяционный метод оказывается полезным для вычисления собственных аначеннй минуя вычисление характеристического поли- нома.
812 ПОЛНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ (гл. Ра Существует следующий метод для определения корней поли- нома') 7(1) (или какой-либо другой аналитической функции'), являющийся несложным обобщением известного способа ложного положения. Берутся три произвольных значения Го, Ео Гд независимой переменной и вычислЯютсЯ соответствУющие значениа фУнкции Уз=у(!о), у,=у((,), уз=у(гд). По нзйденным значениям строится интерполяционный полипом второй степени и находятся его корни.
Тот из корней, который оказался ближе к 1д, чем другой, принимается за следующее приближение бм Далее тем же способом строится !м исходя из тройки чисел дн !д, !д и т. д. Докззательство сходимостн этого процесса, при произвольных начальных приближениях, неизвестно.
Оно известно лишь в предположении о достаточной близости исходных приближений к вычисляемому корню.') Однзко практически процесс оказывается всегда сходящимся. Выбор интерполяционного полинома именно второй степени (а не первой и не более высокой) удобен тем, что при нем без существенных осложнений имеется возможность, в случае необходимости, выхода на комплексную плоскость с вещественной оси, даже ес,ти 7'(г) имеет вещественные коэффициенты и исходное приближение берется вещественным.
Расчетные формулы таковы. Положим Г,— )о — Ьм Гд — ),=Ад сд — (,=Ад. Тогда Ьд есть корень квадратного уравнения аг'+ Ьг+ с = !). при а = Ад(уд уд)+ Ад(уо уд) Ь = Ь, (Ь, + 2дд) (уд — у,) + Ь (уо — уд) (7) с = Ь,Ьд (Ь, + Ь ) у,. Формулы становятся еще удобнее, если ввести отношения поправок, положив (8) д а д д д Для од получим квадратное уравнение айд+ 98+ Т = 0 (9) д) Мюллер (Ма!!ег О.], Майх ТаЫед апд О!Нег АМд Сошро!., 1956, 1О, 208 — 215. д) Франк (ггап$с %.
!..). 1. Аддос. Соври!. Масюпегу, 1958, 5, Ра 2, 154 — 150. $491 мвтод интввполяции с коэффициентами 21У2 .11)+ 21УО 11) ~ = (! + 22,) (у, — У ) + ь,'- (у — у ) Т = (1 + 82) Уа (10) Для решения квадратного уравнения здесь удобна форв1ула (11) р .1. )г 62 421 причем знак при квадратном корне должен выбираться так, чтобы из лвух возможных значений знаменателя получалось большее по молулю. Новая поправка получится по формуле 52 = 5282, новое прибли- жение (12) 42 = 12+ 52.
1) Ф ранк [1!. При применении этого приема к вычислению собственных значений') нет нужды в вычислении коэффициентов характеристического полинома. Вычисление значений характеристического полинома при фиксированных значениях 1 сводится к вычислению численных определителей (А — гЕ(, что возможно производить без особого трупа, например, по методу исключения.
Описанный прием особенно хорошо приложим, если матрица А имеет вил, улобный для вычисления определителей ! А в 1Е ), например, если матрица почти треугольна илн трехдиагональна. Эти сообра1кения дают основания рекомендовать применение квадратичной интерполяции после преобразования исхолной матрицы к почти треугольной форме (например, методом Хессенберга или методом вращений Гивенса, см. 9 51) нли к трехдиагональной (например, биортогональным атгорифмом, см. 9 63, или методом вращений в симметричном случае). В качестве примера вычислим два собственных значения матрицы (4) 9 51. В табл.
!Ч. 13 эта матрица подобным преобразованием првведена к трехдиагональной форме. Возьмем 1,=0, 1, =0.5, 1,=1. Тогда У, = 0.28615247, у, = — 0.01927552, У, = — 0.07370363. Проведя вычисления по формулам (1О), (11), (12), получим 12 = =1.26691 227. Вычисляя опрелелитель ~ А — 1,Е (, получим у, = = — 0.31978253.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
