Бабенко - Основы численного анализа (947491), страница 106
Текст из файла (страница 106)
По поводу. других методов отыскания следу>ощих собственных значений мы рекомендуем читателю обратиться к З 7 настоящей главы либо к специальной литературе (110, 114]. 516 Глава 8, Теория итераций и методы ре1исния некоторых задач Обсуждая метод Гаусса, мы подсчитывали число операций, необходимых для решения системы линейных уравнений, т. е. определили временную сложность метода.
Однако, когда речь идет о проблеме собственных значений и собствешгых векторов, мы можем говорить о ее временной сложности лигпь при условии, что собственные значения должны быть определены приближенно с заданной погрешностью н. Поэтому временная сложность этой проблемы Т1п, г) есть функция и, в. Для отдельных классов матриц и хороших методов функция Т1 и, е) должна иметь мажораиту типа 1чз Т~п., е) < Ап" + Впв(!и — ) Сейчас мы не располагаем необходимой информацией, чтооы указать реальные значения констант А, В, о,,д, ",, а остановимся на этом вопросе ниже. 'й' 6.
Решение нелинейных уравнений и систем уравнений 1. О решении алгебраических уравнений р1г) —.. О, .где р(г) многочлен степени п: р1г) = -" + а1 г" +... + а„1г + а„. Из курса алгебры известно, что при и < 4 уравнение р(г) = О разрешимо в радикалах, т.е. корень уравнения может быть выражен в виде суперпозиции простейгпих бинарных функций — сложения, умножения, деления и радикалов, иначе говоря функций вида ~г а аОднако при п > 4, как утверждает знаменитая теорема Абеля, общее уравнение и-й степени неразрешимо в радикалах. По этой причине, а также потому, что вычисление таких выражений, как ч/а, '/а,..., не может быль выполнено точно 1об этом мы говорили в гл. 1), речь может идти о приближенном решении алгебраических уравнений.
Поэтому большое значение имеет задача о возмущении решений данного уравнения при вариации коэффициентов. Такая вариация неизбежна, поскольку, как правило, машинное представление мпогочлена отличается от исходного. Приведем яекоторые известные теоремы о границах корней многочлена и о вариации корней. Предложение 1. Для любого корня го многочлена 11) имеегп место неравенство ~ а < 2 шах )ая! ~ . 1 -ь:и Доказаткльство.
Пусть и = шах ,'аг~'~~. Поскольку -,", «в< ° ' = — азгви ' —...— аи 1го — а„, то го~" < )аг(; о!и ' ...+)аи — г~ -о -)аи, 'Кб. Рыаснне нслинсйнна; уравнений и сиюпс.н ураанеаий 817 откуда Если о га г < 1/2, то получим неравенство 1 1 г 1 * 1г2 2 (2) (2) 1 — 1г2 что противоречит уеговию. Таким образом, о~го( ' > 1/2, что и доказывает предложение. П 3 а д а ч и. 1.
Докажите, что у многачлена г" — ргг" ~ —... — р . р, где рг >< О (д =- 1, 2, ..., и), рг -' ... — р„> О, поло'кителыь гй корень единственный. 2. Докажите, что если Ь", б — единственные положительные корни много- членов г" — ~аг гн ' —... — (а„бг —,ан' и г" х аг~г" +... + а„г(е — ~а„~, то для любого корня га многочлена (1) имеют место неравенства 8 ( ~ "а < С. 3. Покажите, что корень еа многочлена (Ц удовлетворяет неравенству ыь 1еа,' ч шах (!аь//(Ь)) (2 — 1) Рассмотрим два многочлена - многочлен р(г), определяемый формулой (1), и многочлен у(е) =.
г" + Ььеь г -, '... - Ь„. Пусть хм ..., хн, ум ..., у„ — соответственно корни этих многочленов. В соответствии с предложением 1 введем величину о = шех снах()аь)Пь, )Ьь Пь). 1<в<а Ясно, что шах шах((хь(, ~уь,) < 2ск. 1<а<а Предложение 2 (84).
Предположим, что ~Ьь — аь~ < по" (1с — 1, 2, ..., и). Тогда корни многочленов р(г). О(г) лгоаюно иереяумеровать так, чтобгы выполнялись неравенства ~хь — уь,' ( 4опоП", Ь = 1, 2, ..., и. (2) Часто возникает проблема об относительной оценке погрешности корней многочлена при вариации его коэффициентов.
Пусть даны многочлены р(г) = авва + ... -- а„гг + а„, й(г) = Ьое" + ... + Ь„.де + Ь„, и предпологким, что аоа„ф О; тогда р(л) имеет и корней хг, ..., хн. Предложение 3 (84). Допустим, что илаеют месило неравенства ~1гь — аь~ < т~аь~ ~(й = О, 1...., и), где т < (4и) ". Тогда и корней уг, ..., у„многочлена д( ) можно перенумеровать так, чтобы ~уь — хь,'' < 8ит~~~~хь.', й = 1, 2, ..., и. (3) 518 Глава д, Теорие итераций и методы рееаеиил иекоеаорыт задач Этими предложениями решается задача о непрерывности корней алгебраического уравнения от его коэффициентов.
Ясно, что в общем случае показатель 1,'и множителя о(т) в оценке (2) ((3)) является точныгц в чем нас убеждают простые примеры. Поэтому оценки (2), (3) накладывают непомерные требования малости на вариации коэффициентов многочлена для того, .чтобы были малы вариации корней. Отсюда следует, что задача численного отыскания корней многочленов некоторых классов будет практически некорректной, если только не рассматривать вычисления с многократной точностью. Теория возмущений корней алгебраического уравнения тривиальна. В самом деле, рассмотрим задачу об отыскании корней уравнения р(е) — ' 4(е) =.
О, р(-) = ел+ а1гв + .. где р, д многочлены степени и, в виде рядов по степеням малого параметра е. Если,. простой корень многочлена р(е), то корень много- члена (4) можно разложить в ряд по степеням е: ь е ( ) .=. = --. ~р а, ье . о=1 (5) Это следует из теоремы о неявной функции в случае аналитических функций (теорема о неявной функции для гладких отображений банахова прострщества была доказана в гл. 2), Мы не будем выводить общих формул для определения коэффициентов а, ю а найдем только выражение для а и Подставляя разложенеие (5) в уравнение (4) и сравнивая коэффициенты при е, получим (б) Пусть е — корень кратности г > 1:тогда и поэтому (е) раскладывается в ряд не по целым степеням, а по степеням е~дз, т, е.
-",(е) = + ~ а ьеь7". (7) 1=1 Подставляя это разложение в уравнение (4) и учитывая вид многочлена р(е), получим 'Об. Решение. неггинейнмег уравямгий и еишпем уравнений 519 откуда после очевидных преобразований придем к формуле (8) и тем самым получим г значений для а г, и будем иметь г.
ветвей функции е ( ). Формула (8) показывает, что в предложениях 2, 3 показатель 1гггг не занижен. Ъг!ы не станем доказывать сходимость разложений (5), (7), а будем ими пользоваться для эвристических оценок, ориентируясь на величину главного члена. Как и было ясно априори, кратные корни крайне чувствительны к вариации коэффициентов уравнения. Назовем величину числом вбуеловленносгли корня;„, (кратности г ). Не следует связывать плохую обусловленность корня уравнения, когда а велико, только с его кратностью.
Пусть, например, р„(е) .=- 2 о"" гТ„(2е — 1), где Тн -- многочлен Чебышева первого рода, Корни ри(е) равны х„— —. (1 -' сов де) гг2, О, — -- (2г —. — 1)я,г(2п) (г = 1, 2, ..., и). Множитель 2 -'" г введен для того, чтобы старший коэффициент мпогочлена р„(-) был равен 1. Число обусловленности любого корня х. нетрудно определить; ( 1)г — 1 вгпО 22л — 2 2" 7'„'(2х, — 1) Пользуясь формулой (3.1.6), несложно вывести формулу 2 ""+ т„г2 1г — г в=о Поэтому если примем гг =- 20 и предположим, что коэффициент аго берется с погрешностью, величина которой аго, где к — —. 2 ' (это соответ— го ствует разрядной сетке машины БЭСМ вЂ” 6), то главный член погрешности корня х, на основании формчл (5), (6) будет равен ( — 1)г вшОУ з аго го . — аго 'г, 2 ~ = ( — 1)' — его в1пО, 20 80 причем вкладом остальных членов разложения (5) можно пренебречь, что обосновывается простой., но громоздкой выкладкой.
Вычисляя коэ4>- фициент аш, получим величину погрешности ( — 1)г 26,7... го ейп О . Таким образом, корни е при! = 1, 2, ..., л могут быть вычислены с весьма скромной точностью, которая в лучшем случае при у' = 10 составляет 0,055... 520 Раааа 8, ?сориа игаараиий и иотоди рошоиьа иокоторих задол Хотя многочлен 2 '-" л Г (йг — 1) при и = 20 может быть точно представлен в ЭВМ, но это чистая случайность. Наш вывод не теряет силы, поскольку в процессе вычисления корней скажутся погрешности округления и положение может оказаться еще хуже.
Таким образом, задача нахождения корней многочлена Чебьппева плохо обусловлена. Читатель пе дол>кон думать, что плохая обусловленность возникла из-за того, что корив сгущаются к концам отрезка )О, Ц, Если бы мы взяли корни равноотстоящими, то положение было бы еще хуже, 11з рассмотрешюго примера можно сделать важпьш практический вывод. При отыскании корней ортогональных многочленов нужно пользоваться арифмети кой д в ой н о й т о ч н ос т и,допуская минимальные погрешности прп машинном представлении многочлена.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
