История и методология прикладной математики. Русанов, Росляков (2004) (1185895), страница 26
Текст из файла (страница 26)
Принципиальным является следующий иэ теоремы Вейерштрасса тот факт, что для непрерывной на [«,Ь) функции Пх) ее наилучшее приближение е (г ) -е о при « — ь оо. Однако весьма важны оценки е (У) при конечных «. Такие оценки были получены рядом ученых в первой половине ХХ века. — 131— СК Е (Х) ~ (— С=солях и [1 (х) — Р (х)) «( е, и = «(е), Джексоном дана оценка 1и п ЕяУ) < — СИ, С =. сопэе, и" Имеет место и обратная теорема. — 132— — 133— Приведем некоторые результаты для приближений алгебраическими много- членами функции 1(х), заданной на отрезке [а, Ь).
Следующие две оцении принадлежат Джексону. 1) егли г(х) непрерывна нв [а, ь) и удовлетворяет условию лнпшица с постоянной К, то 2) Если Дх) на [а, Ь) имеет непрерывную производную порядка р, то е (1) < -- — и, [111(х)[< и, с(р) = г. С(р) Бернштейн доказал теорему о том, что для аналитической функции Дх) Е«(1) убывает с ростом и в геометрической прогрессии ЕеЦ) < СО", 0 < о < 1, С = сонэк Им доказана и обратнав теорема о том, что если для функции величина Е (У) убывает с ростом и как член геометрической прогрессии со знаменателем 0 < О < 1, то У(х) — аналитическая функция. Аналогичные оценки были получены для случая приближения функций с помощью тригонометрических многочленов.
Существует теорема Бейерпетресса о том, что для функции Дх), имеющей период 2т и неирерывной на отрезке [ — ег,т), существует тригонометрический многочлен Р (х) степени н такой, что для ллебаго е. Отсюда следует, что величина Е (1) наилучшего ирибли- жения с пОмощью тртгонометричжкого многочлеиа стремитсв к нулю при и -+ оо. если 1(х) имеет непрерывные производные 11ь1(х), и [1:еь1) < И. Как и для случа» алгебраических многочленов справедлива оценка, установленная Бернштейном, для наилучшего приближения аналитической функции Ев(х) ~< Сэв, 0 < О < 1, С = сопэе.
б. В вычислительной практике часто встречается необходимость приближения функций, заданных не на континууме, а на дискретном множестве точек хе, э = О+ел. Значения дискретной функции (Я не определены в точках числовой оси, отличных от х,. Для оценки близости двух дискретных функций используются различные нормы, например, ))1[)о, = гпах)Д), [)1[)р — — ( ~~ гг,)1',)в) с=о Весовые коэффициенты еуг ) О выбираются в завсимости от зав дачи. Часто ставится условие 2 сг, = 1. Обычно используются 1=0 равномерная (р = сю) и квадратичная (р =. 2) нормы.
Как и в континуальном случае аппроксимирующими функциями чаще всего служат многочлены или системы многочленов. Для сравнения дискретной и континуальной функций вводится операция проектирования пространства континуальных функций на пространство дискретных функций. Ее простейшая форма дается формулой д, = д(х,), где д(х) — — континуальная, (д,) - — дискретная функции. Таким образом, 'если Р„(х) — аппРоксимиРУющий многочлен ДлЯ (Я, то его отклонение от (уг) определяется величиной нормы в дискретном пространстве: Многочленом наилучшего приближении Р„" называется такой, который доставляет минимум нормы разности ели.
Доказано, что для 1 < р <+со многочлен наилучшего приближения единственен. Для р = — 2 коэффициенты ае многочлена наилучшего приближения вычисляются столь же просто, как и в континуальном случае, а именно, как решение системы линейных уравнений относительно а, п у ю ю стаха+г ~а, = ~~е Уьхь, э =-- Π— . "и. =О Ь=О а=о ~~ ад/а+д = /а + й», дыд У, — 1У» — (3/35)5'1У» 135— Аналогично вводятся различные виды ортогональных много-",, членов, зависящие от выбора весовых коэффициентов с, и си-: стемы точек хд. Для равномерной нормы вычисление многочле-: на наилучшего приближения для заданной (Я представляет сложную вычислительную задачу, решаемую только последовательными приближеяиями. 6. Близкой к вопросу о среднеквадратичных приближениях.
является задача "выглаживания" значений функции, заданной: таблицей с постоянным шагом. Суть проблемы состоит в следу-. ющем. Пусть /а — табличные значения функции (/а), имею-,. щие некоторую погрешность е», так что /а = /а + еа. Задача' выглаживания состоит в том, чтобы с помощью некоторого ал-'' горитма максимально уменьшить ]е»], не изменяя лри этом /». Очевидно, что в общем виде без дополнительных предположений.' о природе /а и еа задача не имеет смысла. Однако в практике вычислений погрешности ед, обычно можно считать случайными, а /» — значениями некоторой континуальной функции> обладающей определенной степенью гладкости.
При этих допу-,: щениях задача выглаживания может быть точно поставлена и' решена. Итак, допустим, что 1) значения /а представляют собой значения некоторого мно-',! гочлена и-й степени; 2) таблица не имеет систематической погрешности, и все са' представляют собой независимые случайные величины с нуле- ' вым математическим ожиданием и одинаковой для всех диене-( репей Вг. Для построения алгоритма выглаживания введем линейный:.
оператор А, переводящий дискретную функцию дд' вднскретнуэу функцию У, Уа = ~ ~ад»У»~.д или У = А(1У). Пусть оператор А таков, что он сохраняет »У, если бда суть значения многочлена Р„(х) степени, не превосходящей и,". то есть А(Р ) =- Р„или ~~ адР„(ха+ И) = Р (ха). д=дд Применяя оператор А к функции /», получаем 2 --г где йд, = ) адса+д — случайная величина с дисперсией Ю: д=й дд = ~~ ад~~П~ =7~»д~, Уг= ~ад~. Если уг < 1, то задача выглаживания решена. Приведем два примера. 1) и =- 1, тогда Уа = (Уа + об И, = 1У» + гд(бда-д — 25У» + (Уа+д) = г»Ц, д + (1 — 2сд)(У» + а1У» д, уг = гд~+ (1 — 2а) + а = бдг~ — 4а+ 1, 1 1 имеет минимум, равный — при гд = —, и г 3 3' Уа = (й,-д+ (Уа+ 1У»+д)/3. 2) и — — 3, тогда Уд, = »У»+ Р5~1да = Ц, +)д(дда г — 45У» »+ 6»У» — 41/а+д+(Уа~.г), 7г = 706» + 126+ 1 имеет минимулд, равный 17/35 при дд = — 3/35.
Соответствующий алгоритм выглаживания называется выглаживэлием с четвертыми разностями. Эта фор- мула часто применяется на практике и дает хорошие результаты в тех случаях, когда (/а) на отрезках (хд, г,ха+э] достаточно хорошо аппроксимируется многочленом 3-й степени. Ьу=~ ~Ру'(5) (14.4) (14.1) — = /(х,у), 11 у 11х — 136— — 137— 3 14. х1исленное интегрирование дифференциальных уравнений 1.
Первый алгоритм численного решения обыкновенного диф-' ференциального уравнения был дан Л. Эйлером в первом томе, "Иптегрэльсюго исчисления" (1767). Он поставил задачу вычи-' слить решение уравнения если известно значение у = уо при х .= хо. Это, по-всщимому,' первая постановка задачи с начальными данными. Метод, предложенный Эйлером, принято называть методом ломаных илн методом Эйлера.
Он состоит в том, что в близкой к хо точке: х = х1 полагают У1 — — уо + Ч(хо, уо), " =- х1 — хо- (14.2): Аналогично вычисляется уг = ус+ Ч(хс,у1) в т. д. Формула (14.2) получена удержанием первых двух членов ряда Тейлора для у(х) и имеет локальную погрешность О(62) . Ломаной Эйлера можно приблизить интегральную кривую, проходящую через точку хо, уо, если кривая сущесгвуег и единственна.
Математическая теория задачи (14.1) была создана значительно позже появления работ Эйлера. Французский математик Огюстен Коши (1789-1857) показал, что если /(х, у) непрерывна по х и у и удовлетворяет условию Липшица по у, то решение задачи (14.1) существует и единственно. Другое доказательство существования решения задачи (14.1) (но не езинственности) при выполнении только условия непрерывности /(х,у) по обеим переменным дал итальянский ученый Джузеппе Пеано (1858-1932). При этом и Коши н Пеано при доказательстве использовали ломаные Эйлера.
2. Другой подход к построению приближенного решения дифференциального уравнения (14.1) дал немецкий ученый Карл Рунге (1856-1927). Класс этих методов носит название методов Рунге-Кугта. Идея метода заключается в следующем. Значение решения у1 в точке х1 представляется в вцце ряда Тейлора по степеням Ь, т. е. ~1у = у1 уо = ссуо+ уо + — М + .. (14.3) 6 С другой стороны, приращение решения выражается так где Р, = сопэс, Р1 + Рг + . +Р = 1, й1 = Ч(хо,уо), Iсг = Ч(хо + огл УО+ Ргсх1) йз.= Ч(хо+ пзй,уо+ Рзгйс+РзгЫ /с = Ч(хо+ о Ь УО+ Р 1/с1 +Р.гlсг+ ' +Рхх — 1~т-1). коэффициенты р1, - .
Р. ссг ..., ссг Рж~э ° и = 1,..., 1 — 1, выбираются так, чтобы разложение (14.4) совпадало с (14,3) до возможно более высоких степеней А. Очевидно, при г = 1 это мегод Эйлера (14.2). При г = 2 возможны два случая. Если положить Р1 = О, рг =1, ссг=Рг1= 1/2,то 1 1 сс1 = и/(хо~уо) ЧО 2 = Ч(хо+ 2сс УО+ 2 1) з У1 Уо+ 1сг — Уо+ Ч(хо+ 5 УО + ЧО) + с'(5 ).
Аналогично вычисляется решение в точках хг = х1 + 5, хз = хг + 5 и т. д. Этот метод называется методом хорд и имеет локальную погрешность О(лз) . Если выбрать Р1 — — Рг = — 1/2, ссг = 11ы = 1/2, то сс1 ЧО ссг Ч(хо + сс УО + сс1) У1 УО+ (х1+ хг) = УО+ 5[/О+/(хо+ 5)УО+ ЧО)[ + сс(5 ) 2 Зная у1, можно вычислить уг, уз и т. д. Этот метал также имеет на шаге погрешность О(аз) и получил название метода Эйлера с пересчетом. Наиболее употребительна формула Рунге-Кутга при г = 4, Она имеет вид (для точки х1 = хо + 5): 1 Р1 = ро + — (сс1 + 2/с2 + 21сз + /сс) + О(53), 6 где 1 1 101 = »УО 52 = АУ(хо+ А~РО+ — сс1) 2 ' 2 1 1 53 АУ(хо+ А*РО+ с2) ~ос ссУ(х~ + сс ро+ 103).
и„ р» =Р» 1+ / У(х,р(х)) 11х. »„ (14.5) Чтобы вычислить интеграл для функции У(х,р), запишем интерполяционный полинам Нькпона по узлам х», х» +1, ..., х» 1 и используем его на (х„г,х„) вместо У(х,р). Выполнив интегрирование в (14.5), получаем Р» =- Р -1 + сс(ап — 1У» — 1 + 11» — 2У» — 2+ ' ' '+ а»-с»У» — 1п) где У, = У(хс,рс). Наиболее употребительна эта формула при га = 4. Она имеет вид 5 р» =- р» 1+ — (55Уп-1 — 59У вЂ” 2+ 37Уп-3 — 9Уп с). (14.6) Формулы Рунге-Кутта при т < 4 имеют погрешность О(Ь"+1). Однако при г > 5 нельзя получить локальную погрешность О(Ь'), 3 > г + 1, поэтому формулы Рунге-Кутга при г > 4 не используются.
Заметим, что метод Рунге-Кутта — зто одношаговый метод, а все приведенные выше формулы справедливы для случая неравностоящих узлов х, у =- О, 1, 2,.... 3. Другой класс формул численного интегрировании уравнения (14.1) был получен раньше, в 1845 году, английским математиком и астрономом Джоном Адамсом (1819-1892). Идея метода Адамса заключается в слелующем. Рассмотрим сетку равноотстоящих узлов х»,„, х» е1, ..., х» 1, х», ... и предполо- жИМ, Чта РЕШЕНИЕ ИЗВЕСтиа В т уЗЛаХ Хп,п, Х» тж1, ..., Х» Для вычисления р» уравнение (14.1) запишем в виде Формулы такого типа получили название экстраполяционных формул Адамса.
Недостатком их является то, что ошибка экстраполяции может оказаться, на самом деле, очень большой. Обычно в число узлов интерполяции включают узел х», где и требуется вычислить решение. При использовании четырех узлов при интерполяции получим Р» = Р»-1 + (9Уп + 19У» 1 — 5У» — 2 + У» — 3) + О(5 ).
(14.7) Это интерполяционная формула Адамса. В правую часть (14.7) входит У» = У(х„,р»), так что при вычислении р» по этой формуле нужно решать, вообще говоря, нелинейное уравнение. Для этих целей целесообразно использовать метод Ньютона, поскольку имеется хоропсее начальное приближение р» 1. Иногда комбинируют формулы (14.6) и (14.7) - — вначале по (14.6) вычисляют предварительное значение Р», а затем делают несколько 101 итераций, используя (14.7): Р„= Р» — 1+ — М ~+ 19У -.1 — 5У» — 2+ У»-3), 3 = 1,2....
24 Некоторое неудобство, возникающее при использовании метода Адамса„связано с отходом от точки хо, где задано начальное значение ро Если применяется формула (14.6), то кроме ро нужно еще знать Р1, р2 и рз, чтобы начать процесс вычисления. Для их вычисления обычно применяется метод РунгеКутта. Стандартный счет по формуле Адамса (14.6), когда используемые в них значения функции У(х, р) в предыдущих узлах известны,.значительно экономнее метода Рунге-Кутта, в котором на однолс шаге требуется вычислить У(х, р) четыре раза вместо одного. Метод Адамса есть частный случай многошагового метода аьр» ь = И~ ~51У» (14.8) Лпо ьпо при ао = 1, а1 = — 1, ...„ ал = О, й = 2,3,...,т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
