История и методология прикладной математики. Русанов, Росляков (2004) (1185895), страница 23
Текст из файла (страница 23)
А практика требует вычислений собственных значений дли матриц 20-гот 30-го и более высоких порядков. По счастью, во многих случаях нужно знать не все собственные значения, а только одно илн несколько максимальных (или минимальных) по модулю. В этом случае оказывается эффективным применение итерационных методов. Простейший из них следующий. Пусть матрица А имеет не кратное собственное значение Л1, по модулю значительно превосходящее все остальные: :го прн некотором з )Л1) » (ЛЯ >. (ЛЯ », так что выгодно лзять А' вместо А.
Естественно, что это возможно далеко не осегда. В общем случае итерационные методы также не решают проблемы собственных значений. В чем же все таки дело? Почему, посмотря на значительное увеличение числа знаков мантиссы, погрешности результата оказываются очень большими даже при решении самой системы, не говоря уже о собственных значениях. (Отметим, что в некоторых работах 40-х годов прошлого нека утверждалось, что для решения систем с 50 неизвестными прямыми методами с точностью до 5 знаков необходимо иметь мантиссу с 100 десятичными знаками). По нашему мнению, для того имеются по крайней мере две причины. Одна нз них и, как показало время, главная состоит в том, что рост погрешности результата обусловлен ростом погрешностей округления вследствие неустойчивости алгоритма решения.
Другой причиной является то, что в некоторых случаях относительная по- ~ решность округления может оказаться аномально большой нз ~а сокращения знаков при вычитании (сложении чисел разных члзных знаков). Простой пример показыиает, как зто происходит. Пусть требуетс» аысеслить еелнчину х = 10 (ъ72.00003 — т/2). Вычисление с 10 знаками и злаеаюшей запятой дает х = 1.061000000.
Результат еычислении с 20 зна; ,амн -- е — 1 0606597740 И, наконец, результат вычисления с 10 знаками лссле известного преобразоеания: 10 = 1.060659774. 2.00005 - 2 т 2.00005+ г П периом случае имеем потерю 5 6 знаков. Случай с преобразованием не Хает потери точности, однако он не применим при массовых расчетах. Полагая, что приведенная в примере ситуация встречается достаточно редко, можно исправить положение, увеличив число знаков.
Но никаким реальным увеличением числа знаков нельзя победить неустойчивость алгоритма. Эта задача, то есть создание устойчивых алгоритмов для численного решения задач линейной алгебры, решалась многими исследователями. Сначала было выяснено, что некоторые матриць1 специального вида допускают достаточно простые и ссгойчивые прямые алгоритмы (иапример, трекдиагональные матрицы). Устойчивые прямые методы были развиты также для — 111— Су1цествует много других иитерполяциониых формул однако при использовании одних и тех же узлов хе, х1, ..., х„все они приводят к единому иитерполяциоиному многочлену степени и. Формула Ньютона, приведенная в 3 7, использует разности вперед и удобна, если х находится в начале таблицы. Если использовать разности назад, получим другой вид формулы Ньютоиа. Известны формулы, использующие центральные разности.
К иим принадлежат интерполиционные формулы Гаусса, Стирлинга, Бесселя, Эверетта. В каждом конкретном случае удобнее пользоваться той или иной формулой. Был разрабатан и общий подход получения иитерполнциоииых формул. Фраипузский математик Шарль Эрмит в 1878 году сформулировал обобщенную задачу интерполирования функции 1" (х), имеющей на [а, Ь] необходимое число непрерывных производных, Оиа заключается в следующем.
Пусть на отрезке [а, Ь] заданы узлы интерполирования хо, х1, ..., х, в которых известны У(х.), У'(х,), - -, Х( ' ')(х,), 1=9ь то есть всего 11е+ 111+ + пм величин. Требуется построить алгебраический многочлен Н„(х) степени «е+а1+ ° +о — 1, для которого Н(') =У(')(,), =Опа, Ь=О=:«,— 1. Многочлен Н„(х) (Негшгйе) существует и единственен. Он называется многочленом Эрмита. Если интерполяциоиная функция Дх) периодическая, то зачастую удобнее пользоваться ие алгебраическими, а тригонометрическими многочленами. Такие многочлены были получены, в частности, Гауссом в 1805 году. 2.
Вернемся к классической задаче интерполирования. Иитерполяционные миогочлены совпадают с )'(х) в узлах интерполировании. Однако возникает вопрос о величине отклоиения Ап(х) от 1(х) в пРоизвольной точке отРезка [а,Ь]. ПодчеРкием, что иитерполяциониые миогочлеиы получены без каких- либо требований гладкости Дх). Если предположить, что ((х) имеет непрерывную (п + 1) -ю производную, то для остаточного члеиа Н (х) =- 1(х) — 7„(х) — 114— можно получить формулу (в форме Коши) а(а+1) (ьа) Д„(х) = — ш(х), с б [а, Ь], (г + 1)! и оценку ]Н (х)] < М +1, ]ш(х)] (и+ 1)! где фа+1)(с)[ < Ып+1 иа [а,Ь]. если есть свобода в выборе узлов интерполирования хе х1, ..., х„, то погрешность можно уменьшить, минимизируя величину 1пах ]ш(х)] =- п1ах ](х — хе)(х — х1)... (х — х„)].
(12.3) ав(ад) ав(а,б) Это можно сделать, опираясь на фуидаме~тальные результаты, полученные П. Л. Чебышевым, который в 1859 году в работе "Вопросы о наименьших величинах, связаиные с приближенным представлением функций" развил теорию наилучп1его равномерного приближения функций многочлеиами. Первые р1пультаты были им опубликованы в 1854 году в статье "Теория механизмов, известных под названием параллелограммов" в связи с исследованием прикладной задачи по кинематике шарнирных механизмов. Здесь были сформулированы условия наилучшего приближения и получен многочлеи, наименее уклоняющийся от нуля на отрезке [а, Ь] среди всех многочлеиов данной степени с коэффициентом единица при старшей степени. Такие многочлены называ1отся многочлеиами Чебышева и обозначаются Т(х) (от французского написания фамилии Чебышева — ТзЬеЬуайе)7).
Минимум (12.3) достигается, если ш(х) есть многочлен Чебышева (Ь вЂ” а)" + 2х — (а+ Ь) 1 ш(х) = Т„+1(х) = ха+1 сов [(11+ 1)агссов Ь ) корни которого суть а+Ь Ь вЂ” а (21+1)я Х1 =- 2 2 2(п+ 1) + — соз ! — 115— При этом величина (12.3) будет такой: (Ь в)п+! шак ]ь!(х)[ = эе1а,ь1 2~+! и для остаточного члена справедлива оценка М„+! (Ь вЂ” а)"+! ]Я„(х)[ < —- (и ! 1)! 2зь+! Величину й„можно пытаться уменьшить, увеличивая число узлов на [а,Ь]. Возникает вопрос о скодимости: будет лн й„(х) -+ О при и — > со ? Вообще говоря, нет. Сходимость интерполяционного процесса в точке х* б [а, Ь] означает, что существует 1пп А„(х') = 7'(х ). Равномерная скодимость на [а, Ь] л — ню означает, что шах ]!'(х) — А„(х)] -+ О.
яе[ад1 Большой вклад в теорию приближений функций внес другой русский математик С. Н. Бернштейн. В частности, он показал, что для функции Дх) —.— ]х] на отрезке [ — 1,1] последовательность Ь„(х), построенная по равностоящим узлам, при и -+ оо не сходится к ]х] ни в одной точке [ — 1,1] кроме х = — 1,0,1. Более того, интерполяционный многочлен при 'л -+ сю совершает неограниченные колебания между узлами. Немецкий ученый Фабер доказал, что никакая последовательность узлов не гарантируетсходнмости процессаинтерполяциидля пронзнольной неярерывной функции. Более точно: какова бы ни была последовательность узлов, найдется непрервнэя на [а,6] функция Дх) такая, что последовательность интерполяпдонных многочленов не сходится к Дх) равномерно на [а,Ь]. Таким образом,не существует универсальной системы узлов интерполяции, обеспечивающей скодимость для любой непрерывной функции.
Однако для каждой непрерывной на [а, Ь] функции можно подобрать систему узлов, чтобы интерполяционный процесс сходился равномерно на [а,Ь] (Марцинкевич). Подчеркнем, что построить такую систему, свою для каждой функции, весьма сложно. Если 7'(х) — глад!сая функция, то есть Дх) и 7"'(х) непрерывны, то чебышевсквл система узлов обеспечивает равномерную сходимость интерполяцнонного процесса. — 116 —.
й. Приближать у(х) на всем промескутке [а, Ь] нпгерполяционным многочленам высокой степени нецелесообразно из-за возможных больших погрешностей. Это связано с накоплением погрешностей округления и возможной расхсдимостью интерпо;ощионного процесса. Выгоднее разбивать отрезок [а, Ь] на частичные отрезки и на каждом из пик заменять функцию Дх) многочленом невысокой степени.
Это так называемая кусочнополиномиальная интерполяция. Важным применением кусочно-полияомиальной интерполя~сви является аппроксимация дифференциальных выражений на равномерной сетке. Рассмотрим функцию 1 (х), имеющую и+ 1 производную на некотором отрезке [а, Ь] оси х. Введем равно- черную сетку хь с шагом Ь, покрывающую отрезок [а,6], так *с!о хс, = хе+ ЬЬ, Ь = О, х1, х2,.... Сопоставим каждому отрезку [хю ха+!] интерполяционный многочлен и-й степени Х„д(х), ,пспроксимирующий функцию 7(х) и построенный по точкам хь хь +с, °, хы ха+! " " хь+ э )О, сч>О, пс+ьг=-п. Погрешность аппроксимации 7(х) на отрезке [хы хе+!] дается формулой [1(х) — Ь„л(х)] <,Мя+!. ИхП Гак как при любом 1, — и! < 1 < из, ]х ха+!] < ха+ э хь — ю ~ — (!'! + из)Ь =" пЬ~ го +1 ]! (х) — ь„ь(х)] < - — М„+!6"~ .
(и+ 1)1 Функция Л(х) = Дх) — Х„ь(х) обращается в нуль в и + 1 !очке хс, — и! < 1 < из. Отсюда по теореме Ролля следует, что (х) является интерполяционным многочленом для 7'(х), ложь ~троенным по и точкам с! б (хс,хс+!), 1= 1с — ис, 1с — и!+ 1,, 1с+из — 1. — 117— Рассматривая последовательно Фа)(х), е = 1,2,, п, полу-'' чаем, что для погрешности аппроксимации производных Е(е)(х), производными Е„ь имеет место оценка (а) а+1 — а У1*1( ) — Е~'а(х)] ( М +16"+' ', э = О,),...,п, (и+ 1 — и)! определяющая уникальное свойство кусочно-полиномиальной: интерполяции иа равномерной сетке по сравнению с другимя:, способами аппроксимации (полиномиальные приближения в сте-' пенных нормах, дробно-рациональные приближения, непрерыв-'.
ные дроби и др)!. Можно сказать, что все конечно-разностные' методы численного решения дифференциальных уравнений ос-.' нованы на приведенной оценке близости производных исходной:" и аппроксимирующей функций. Рассмотрим теперь кусочную интерполяцию на всем отрез-' ке (п,Ь] при фиксированном шаге сетки 6, так что хо =- а„' х, = а+ 16, х„= 6 и Ь вЂ” а = пlг. Пусть Е(х) аппроксимирова,' на функцией Я(х), определенной на каждом частичном отрезке'. [хпх;+1] формулой Я(х) .= Еп,;(х), где Е,шл(х) — мнопэчлен'. степени и, и 5(хг) = Е(хс) для всех 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
