Бабенко - Основы численного анализа (947491), страница 66
Текст из файла (страница 66)
Итак, вычислительный алгоритм это тройка (Тг...С, Т ), где В блок управ»ения, осуществляющий отображения множества (Т, ) на множество (Ти). Как было показано выше, таблипа характеризуется рядом параметров, и самые важные из них - — это ее длина >'>> и то тости „. Ввод алгоритма -- таблицу Т "- будем характеризовать сердиной Л. Вывод алгоритма -- таблипу Т„- будем характеризовать ее точностью =".
По определению точное>тью алгоритма будем считать величину -- точность таблицы на выходе из алгоритма. Скажем несколько слов о принятых определениях. Совершенно ясно. что определения ввода и вывода, сделанные вылив, и их характеристики отражают реальное положение вещей. Вводимая в алгоритм информация характеризуется прежде всего ее объемом; вопрос о ее точности бессмыслен, пока ее объем но указан, Кроме того. таГ>липа Т, подаваемая на вход„ должна быть оптимально устроена с точки зрения наиболее точного нахождения элемента >Л Л отсюда следует, что она при данной длине может вовсе не обладать оптимальной точностью.
Примеры, где встречается такая ситуация, мы находим сплошь и рядом, и они будут указаны ниже. Поэтому информацию на входе следует характеризовать ее объемом. Все остальные характеристики, как, например, точность, являются производными и не дают истинного представления о вводе. Алгоритм условимся обозначать через 0(Х, е), указывая объем информации на входе и точность е, с которой мы определяем элемент у =. Ат. В заклк>чение подчеркнем еще ргз, что, говоря о таблицах функций, мы не имеем в ви,чу, что таблица это ряд значений (вообще говоря„ приближенных) функции в узлах.
Функция может быть задана, например, некоторой формулой, а точнее цепочкой формул, содержащих функции из класса простейших функций, к которым применяются операции суперпозиции, рекурсии и т.п. Тогда длина цепочки будет характеризовать обьем таблипы. Как это ни странно,мы не имеем развитой теории производства приближенных вычислений, основанных на оперировании с функциями как с формулами. В этом отношении мы делаем лишь первые шаги. Когда функции представлены как отображения и, стало быть, в машине представлены таблицами, мы довольно умело с ними обращаемся. 2.
Оценка максимальной точности. Важнейшим вопросом теории численных алгоритмов является вопрос о максимально возможной точности определения элемента й = Ат при заданном объеме информации об элементе т. Введем вспомогательную функцию, которая в дальнейшем будет играть существеннук> роль.
Пусть е(Х; рг') = шЯ(е: Н(г; Х) ( Аг). 314 Глава 5. Общие свойство, вьгчислителънмх алгоритмов Функция е(Х: Х) корректно определена, поскачьку на основании теоремы 3 6 2 гл. 4 функция Н(е: Х) непрерывна справа. Теорема 1. Если на вход в алгоритм, реалггзуюи1ий численное вычисление элемента у .= Ах, иодае. ися таблииа длиной Х, то иогрешносгиь с удовлетворяет неравентиву (2) -„- ) (У; Х). Доказаткльство. Множество таблиц на входе в алгоритм 0 перерабатывается управляюшим бпоком 2 в множество таблиц элементов у е У, и мы получаом таблицы точности е.
Поэтому таблицы на входе в 0 можно принять за таблицы компакта 1', а сам алгоритм за расшифровывающий алгоритм таблицьг. Согласно предложению 1 Э 3 гл. 4, Х > Н(г; У), откуда в силу (1) получаем (2). П Понятно, что доказанная теорема дает важный критерий оценки качества реальных вычислительных алгоритмов по тому, насколько точность алгоритма г превышает величину е(У; Х). Впервые такие оценки даны в (166, 167], Алгоритм 0 будем называть оитимальньгм, если его точность г удовлетворяет неравенству . < Се(У: Х), где С не зависит от Х при Х ~ ЭХО(11).
Мы рассмотрим ряд задач и исследуем некоторые ходовые алгоритмы их решения с точки зрения их оптимальности. Попутно в ряде случаев мьг укажем и оптимальные алгоритмы. 3 2. Анализ некоторых вычислительных алгоритмов 1. х1ислениое дифференцирование. Начнем с задачи численного диг]гференцирования. Пусть в пространстве С(1] (1 = (ое Ь]) задан компакт Х = И",(М; 1) О (Х е С(1]: Х]сс < ь), который мы ниже будем обозначать через И" (ЛХ, 1; ХЬ Пусть А = аи,гдх', з < г, г — з = г, У = А(Х).
Ясно, что Игг (ЛХ, ЛИ 1), где Хг = з) (Ь вЂ” а)"'Х. С другой стороны, имеем неравенство (2.2.15) ХР)] < г1 гггагс(] г 1 — и/с Х(с) (, г)еи] г~ ) где ЛХ„, зависит только от г, з ггг. Поэтому У С И" (ЛХ, Хг, 1), где Ег .—.. ЛХ,гХ,г 'гсЛХ'г', и, следовательно, в силу теоремы 1 з4 гл. 4 Н(г; У) = (ЛХ(е) 1 (Ь.- а), если е < ео. Отсюда е(У: Х) = (Ь вЂ” а)гЛ1Х г. Опишом алгоритм численного дифференцирования. На входе в алгоритм возьмем оптимальную таблицу, построенную в и, '! э'4 гл.
4. Пусть Ь' 2. Анализ нетотпорьта оачиелиотельтта олгоритпмоо 315 Ь--шаг сетки,1 = а-еХЬ (Х = О, 1, ..., и) .--узлысетки. Если нам нужно вычислить производную в точке т и (ть, хь+т'„то в качестве приближенного значения г-й производной возьмем рбй(а: Х), где р(а; Х) интерполяционный многочлен Лагранжа, построенный по узлам амь (Х = — О, 1, ..., г — 1). Полагая в неравенстве (3,6.7) Ь вЂ” а —... г6 и принимая д = ЛЫ', получим ХОО(,) — ррй(.л Х)) < С„,ЛХЬ.'. Поскольку 6 = (Ь вЂ” а)(п, и =- Х, где т' длина таблицы, в силу послоднего неравенства производная будет определяться с погрешностью е < Р„,(Ь -- а)тЛХЛтт.
(2) Если Ь < (г,т21', либо Ь > п — /т Х'21 при нечетнолл т., либо й > и, — (гтт2, :+ -Ь 1 лри четном г, то в ттостроении нужно сделать очевидные изменения. Из (1), (2) вытекает оптимальность тйтедложенного алгоритма. Замкчяник 1. В исследовании алгоритма дифференцирования мы допустили небольшую неброжностть поскольку пе учли, что ртот (т; Х) будет вычисляться с помощью операций пад округленными числами. При фиксированном г это вызовет потерю 0(1) значащих цифр и не повлияет па окончательный результат. Злмкчаннк 2. Если в результате работы алгоритма дифференцирования требуется построить таблицу функции Х'т'т(л), то можно опять воспользоваться оптимальной таблицей для класса И'т,(ЛХ; Х). Злмкчлник 3. В рассматриваеъюй задаче реализуется как раз тот случай, когда таблицу на входе можно однозначно характеризовать ее точностьнт е,.
По доказанному точность определения производной е = ЛХ'Х'е, 'Х'. Отсюда вытекает, что если у функции Х(т) количество знаков брать в согласии с точностью оптимальной таблицы и далее в вычислениях удерживать то же количество знаков, то у г-й производной доля верных знаков равна 1 — гттг (мы говорим о вычислениях с фиксированной запятой).
2. 'Численное интегрирование. Рассмотрим задачу об интегрировании функций, ограничиваясь случаем одной переменной. Приводимые ниже рассуждения остаются в силе и при исследовании краевых задач. Введем одно определение, удобное при работе с таблицами. Пусть Р и Х С: С(Р', —.
компакты. Многие распространенные виды таблиц состоят из набора значений функции, либо из значений функции и ее некоторых производных, либо нз набора значений локальных функционалов. Мы говорим, что функционал .р лоха,льный и сосредото тетт в тиочке. то, если тр(Х) — "- ~о(д), как только Х и д совпадают в сколь угодно малой окрестности точки ао, Такого рода таблицы будем называть таблицами интерполяционного типа. ь!тобы дать более точное определение, угчовпмся называть 316 Гласа 5. Обиьие свойстоо, вьечислитсльнмс алгоритмов окрестностью конечного числа узлов (ть, ..., х„) множество, состоящее из объединения окрестностей точек х (1 = 1, 2, ..., т).
Если диаметр каждой из окрестностей не превосходит , то будем говорить об и-оьрестности множества узлов. Примем следующее определение. Пусть Ту таблица элемента 1 е Х, длина которой равяа Х; зту таблицу будам называть таблицей интсрполяциопного типа, если найдется Хв < Х таких узлов хг, ..., х,у„, что для любого элемента д ~ Л, совпадакьщего с 1 в некоторой г-окрестности ьшожества (хг, ..., аль), будем иметь Тв .-- Т1, Сами узлы и их количество определяются данным видом таблипы, а не взятым элементом 1, при этом число узлов интерполяции и точность задания функции в этих узлах одни и те же для всех функций компакта Х.
Пусть 7 = ,"а, Ь), Х = И" (Л1, Тк 1) и (А1)(х) = ) 1(Ь)сй.. Положим а У вЂ”.. А(Х); ясно, что У с И" ьг(Л1, ТП 1), где Тч —.. ЦЬ вЂ” и). Поэтому (1'; Х) < с(Хо, 'Х), где Хо = И"" (Л1, Тч; 1), и поэтому по теореме 1 34 гл. 4 г(У: Х) < СЛ1((Ь -- а)1Х)" '~., (3) где С константа, зависящая только от г. Допустим, что П(Х, ) — алгоритм интегрирования, у которого на вход подаются таблипы интерполяционного типа. Пусть Ьо Е 1 Ц = 1, 2,..., Хо) соответствующие узлы. Разделим интервал 1 па 2Хо г уо равных частей: 1 = () 1,, и пусть 1а, (/с = 1, 2,....
Р) — те интервалы, 1= для которых 1пс 1„„не содержит ни одного из узлов си Ясно, что Р > Хо. Пусть р е С" ( — сю, оо) -- вспомогательная функция, вводенная прп доказательстве продложения 2 Ь 7 гл. 3 и дополнительно нормированная условием р(1)11 = 1. Если хь --- центральная точка, Ь --- длина интервала 1„ь, то положим ,рг(х) = др(3(х -- хь)(Ь), Ь = 1, 2,, Р, где б определено из условия рь е Х. Так как рв — — Ъ ЯЬ)'р с'1 (3(х — хь)/Ь), то достаточно положить Б = (Ь~З)сЛХ/ так~ р1'"16 Пусть 318 Гласа 5. Оби1ис соойсспоо, оъшислигпслъиих алаоритмоо Но Л', и ауо --- меры количества информации. подаваемой в алгоритм и получаемой в результате работы алгоритма.
Таким образом, налицо огромная потеря информации, характеризуемая величиной (4). Эта потеря вызвана вовсе не тем, что производятся действия над округленными величинами и возможны рост погрешностей округления и потеря значащих цифр, а несовершенством алгоритмов, основанных на применении таблиц интерполяционного типа (а тем более на применении квадратурных формул). Квадратурные формулы не учитывают рост гладкости функции при интегрировании, и, соответственно, повышение точности при той же длине таблицы. Такое же положение имеет место и при решении краевых зццач, и при интегрировании обыкновенных уравнений. Правда, когда мы имеем дело г обыкновенными дифференциальными уравнениями, этот факт завуааирован в тех случаях, когда правые ~асти уравнений задаются в виде формул, т.
е, когда налицо неограниченная информация об исходных данных. 3. 'Численное решение краевой задачи. 2Келая избежать теоретико-функциональных и аналитических трудностей, связанных с самой краевой задачей, мы рассмотрим задачу Дирихле дня уравнения Пуассона ограничиваясь краевой задачей с периодическими граничными условиями, Относительно правых частей предположим, что 1 припадл< >кит классу П', где г нецелое. Уточним определение этого класса; при г целом об этом классе упоминалось в замечании, сделанном в коппс и. 7 З 1 гл. 3. Пусть .0 область в В~. Расхмотрнм класс Н„"(М; Р) с () 1Фс ь>о (Х; Р), где т = (г, ..., г), Ь = (1„..., А). Ниже рассматривается случай р = со, и поэтому все функции класса будут непрерывными и иметь непрерывные производные соответствующих порядков (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
