WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 


Pages:   || 2 | 3 |

«П. Н. Корнюшин ЧИСЛЕННЫЕ МЕТОДЫ © Издательство Дальневосточного университета 2002 ВЛАДИВОСТОК 2002 г. 2 СОДЕРЖАНИЕ СОДЕРЖАНИЕ Аннотация Рецензия на учебное пособие П.Н. Корнюшина Численные ...»

-- [ Страница 1 ] --

ДАЛЬНЕВОСТОЧНЫЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ТИХООКЕАНСКИЙ ИНСТИТУТ

ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ И ТЕХНОЛОГИЙ

П. Н. Корнюшин

ЧИСЛЕННЫЕ

МЕТОДЫ

© Издательство Дальневосточного университета 2002

ВЛАДИВОСТОК

2002 г.

2

СОДЕРЖАНИЕ

СОДЕРЖАНИЕ

Аннотация

Рецензия на учебное пособие П.Н. Корнюшина «Численные методы»

Методические указания для студентов

Модуль 1. Введение. Разностные уравнения

1.0. Введение

1.1. Разностные уравнения

1.1.1. Сеточные функции

1.1.1.1. Сеточные функции и действия над ними

1.1.1.2. Разностные аналоги формул дифференцирования произведения и интегрирования по частям.. 1.1.2. Разностные уравнения

1.1.2.1. Разностные уравнения

1.1.2.2. Уравнение первого порядка

1.1.2.3. Неравенства первого порядка

1.1.2.4. Уравнение второго порядка с постоянными коэффициентами

1.1.2.5. Примеры

1.1.2.6. Разностное уравнение второго порядка с переменными коэффициентами. Задача Коши и краевая задача

1.1.3. Решение разностных краевых задач для уравнений второго порядка

1.1.3.1. Решение разностных краевых задач методом прогонки

1.1.3.2. Устойчивость метода прогонки

1.1.3.3. Другие варианты метода прогонки

Модуль 2. Решение уравнений и задачи интерполяции

2.2. Численное решение алгебраических и трансцендентных уравнений

2.2.1. Задача отделения корней

2.2.2. Вычисление значений корня с заданной точностью. Метод итераций

2.2.3. Метод итераций для системы уравнений

2.2.4. Принцип сжатых отображений

2.2.5. Об одном принципе нахождения сходящихся итерационных процессов

2.2.6. Метод хорд (секущих) и метод деления пополам

2.2.7. Метод Ньютона (метод касательных)

2.2.8. Вычисление значений алгебраического полинома

2.2.9. Метод Лобачевского нахождения корней алгебраических многочленов

2.3. Теория интерполирования

2.3.1. Задача интерполирования в линейном пространстве

2.3.2. Интерполяционный полином Лагранжа

2.3.3. Формула остаточного члена полинома Лагранжа

2.3.4. Оценка остаточного члена формулы Лагранжа

2.3.5. Понятие о разделенных разностях

2.3.6. Интерполяционная формула Ньютона

2.3.7. Основные задачи в теории интерполирования

2.3.8. Сплайн-интерполяция

Модуль 3. Численное интегрирование и решение систем алгебраических уравнений

3.4. Численное интегрирование

3.4.1. Задача приближенного вычисления определенного интеграла

3.4.1.1. Квадратурные формулы с наилучшей точностью для данного класса функций

3.4.1.2. Квадратурные формулы с наилучшей степенью точности

3.4.1.3. Интерполяционные квадратурные формулы

3.4.1.4. Замечания к использованию квадратурных формул

3.4.2. Квадратурные формулы Ньютона-Котеса

3.4.3. Частные случаи формулы Ньютона-Котеса

3.4.3.1. Формула прямоугольников

3.4.3.2. Формула трапеций

3.4.3.3. Формула парабол (Симпсона)

3.4.4. Квадратурные формулы Гаусса

3.5. Численное решение систем линейных алгебраических уравнений

3.5.1. Системы линейных алгебраических уравнений

3.5.1.1. Системы уравнений

3.5.1.2. Частные случаи систем

3.5.1.3. Прямые и итерационные методы

3.5.2. Прямые методы

3.5.2.1. Метод Гаусса

3.5.2.2. Метод квадратного корня

3.5.2.3. Связь метода Гаусса с разложением матрицы на множители

3.5.3. Итерационные методы

3.5.3.1. Метод итераций для решения системы линейных алгебраических уравнений

3.5.3.2. Метод простой итерации

3.5.3.3. Метод Зейделя

3.5.3.4. Метод релаксации

Модуль 4. Линейное программирование

4.6. Основы линейного программирования

4.6.1. Основы математического программирования

4.6.1.1. Оптимальное планирование и линейное программирование

4.6.1.2. Математическая модель задачи линейного программирования

4.6.1.3. Классификация задач линейного программирования

4.6.2. Графический способ решения задачи линейного программирования

4.6.2.1. Геометрический смысл линейных неравенств

4.6.2.2. Геометрический смысл задачи линейного программирования

4.6.2.3. Задачи

4.6.2.4. Обобщение геометрической интерпретации на многомерный случай

4.6.2.5. Алгебраическая характеристика вершины многогранника ограничений

4.6.3. Симплексный метод

4.6.3.1. Геометрическая подготовка

4.6.3.2. Жордановы исключения

4.6.3.3. Опорное решение, опорный план

4.6.3.4. Улучшение опорного плана

Глоссарий

Литература

Учебное пособие содержит основные положения численных методов, относящихся к решению разностных и алгебраических уравнений, приближению функций, интегрированию, задачам алгебры и оптимизации, решению обыкновенных дифференциальных уравнений.

Пособие предназначено для студентов вузов, изучающих основы вычислительной математики.

Рецензия на учебное пособие П.Н. Корнюшина «Численные методы»

Написать учебное пособие по численным методам при наличии трудов таких классиков вычислительной математики, как Н.С. Бахвалов, И.С. Березин, Н.П. Жидков, А.А. Самарский и др.

– задача очень неблагодарная, поскольку все основные методы вычислений описаны с различными уровнями подробности. Правда, пока еще не встречалось учебного пособия, предназначенного для дистанционного обучения. К тому же, данное учебное пособие предназначено для студентов, только начинающих освоение элементов вычислительной математики. Поэтому перед автором стояла непростая задача при сохранении относительной строгости изложения сделать материал в достаточной мере доступным для понимания. Поэтому, по-видимому, не следует требовать в каждом конкретном случае строгости при доказательстве теорем существования и единственности, если задача изложена на понятном качественном уровне.

Цель, поставленная автором пособия, на мой взгляд, достигнута. Пособие написано достаточно понятным языком. Изложены Основные методы вычислений. К тому же, по сравнению с традиционным содержанием, в курс включены разделы линейного программирования, что особенно важно для студентов экономических специальностей.

В целом, издание учебного пособия, в особенности в электронном виде (с учетом дефицита именно такой продукции), – необходимо и актуально.

1) Консультации можно получить по адресу: г. Владивосток, ул. Суханова 8, ДВГУ, ауд. 76 или по электронной почте: korn@ifit.phys.dvgu.ru.

2) Форма аттестации по курсу – компьютерное тестирование в соответствии с прилагаемыми тестами.

3) Нормы аттестации: сдача каждого из 4-х тестирований, соответствующих 4-м модулям, не менее чем на «удовлетворительно».

Бурное развитие средств вычислительной техники привело к подлинно революционному преобразованию науки вообще и математики в особенности. Увеличение возможностей теоретического изучения привело к изменению технологии научных исследований. Решение крупных научно-исследовательских проблем, таких как проблемы овладения ядерной энергией и освоения космоса, стало возможным лишь благодаря применению математического моделирования и новых численных методов, предназначенных для компьютеров.

В настоящее время можно говорить о появлении нового способа теоретического исследования сложных процессов, допускающих математическое описание, – вычислительный эксперимент, т.е. исследование проблем средствами вычислительной математики. Существо этого способа можно пояснить на примере решения некоторой проблемы.

На первом этапе формулируется задача, которую надо решать. Сначала выбирается некоторое приближение или содержательная модель процесса (физического, биологического, экономического и т.п.), решается вопрос о том, какие факторы надо учесть, а какими можно пренебречь.

Содержательной модели ставится в соответствие математическая модель, т.е.

математическое описание процесса с помощью алгебраических, дифференциальных, интегральных и других уравнений. Полученную математическую модель необходимо исследовать соответствующими математическими методами. Надо установить, правильно ли поставлена задача, хватает ли исходных данных, не противоречат ли они друг другу, существует ли решение поставленной задачи и единственно ли оно. На этом этапе используются методы классической математики.

Второй этап вычислительного эксперимента состоит в построении приближенного численного метода решении задачи, т.е. в выборе вычислительного алгоритма. Под вычислительным алгоритмом понимают последовательность арифметических и логических операций, при помощи которых находится приближенное численное решение математической задачи, сформулированной на первом этапе.

На третьем этапе осуществляется программирование вычислительного алгоритма и на четвертом этапе – проведение расчетов на компьютере. Разработка конкретных численных алгоритмов и их программирование на компьютере достаточно тесно связаны.

Наконец, в качестве пятого этапа вычислительного эксперимента можно выделить анализ полученных численных результатов и последующее уточнение математической модели. Может оказаться, что модель слишком груба – результат вычислений не согласуется с экспериментом, или что модель слишком сложна, и решение с достаточной точностью можно получить при более простых моделях. Тогда следует начинать работу с первого этапа, т.е. уточнять математическую модель, и снова пройти все этапы.

Следует отметить, что вычислительный эксперимент – это, как правило, не разовый счет по стандартным формулам, а, прежде всего, расчет серии вариантов для различных математических моделей.

Вычислительные алгоритмы имеют некоторые характерные особенности, что определяет ряд предъявляемых к ним требований. Разработка и исследование вычислительных алгоритмов и их применение к решению конкретных задач составляют содержание очень большого раздела современной математики – вычислительной математики. Вычислительную математику в широком смысле этого термина определяют в настоящее время как раздел информатики, изучающей круг вопросов, связанных с использованием компьютера, и в узком смысле – как теорию численных методов и алгоритмов решения поставленных математических задач. В данном курсе будем иметь в виду вычислительную математику в узком смысле слова.

Общим для всех численных методов является сведение математической задачи к конечномерной. Это чаще всего достигается дискретизацией исходной задачи, т.е. переходом от функций непрерывного аргумента к функциям дискретного аргумента. После дискретизации исходной задачи надо построить вычислительный алгоритм, т.е. указать последовательность арифметических и логических действий, выполняемых на компьютере и дающих за конечное число действий решение дискретной задачи. Полученное решение дискретной задачи принимается за приближенное решение исходной математической задачи.

При решении задачи на компьютере мы всегда получаем не точное решение исходной задачи, а некоторое приближенное решение. Чем же обусловлена возникающая погрешность?

Можно выделить три основные причины возникновения погрешности при численном решении исходной математической задачи. Прежде всего, входные данные исходной задачи (начальные и граничные условия, коэффициенты и правые части уравнений) всегда задаются с некоторой погрешностью. Погрешность численного метода, обусловленную неточным заданием входных данных, принято называть неустранимой погрешностью. Далее, при замене исходной задачи дискретной задачей возникает погрешность, называемая погрешностью дискретизации или погрешностью метода. Например, заменяя производную u’(x) разностным отношением (u(x+x)u(x))/x, мы допускаем погрешность дискретизации, имеющую при x 0 порядок x. Наконец, конечная разрядность чисел, представляемых в компьютере, приводит к погрешностям округления, которые могут нарастать в процессе вычислений. Естественно требовать, чтобы погрешности в задании начальной информации и погрешность, возникающая в результате дискретизации, были согласованы с погрешностью решения на компьютере дискретной задачи.

Сказанное означает, что основное требование, предъявляемое к вычислительному алгоритму, – это требование точности. Оно означает, что вычислительный алгоритм должен давать решение исходной задачи с заданной точностью 0 за конечное число Q() действий.

Алгоритм должен быть реализуемым, т.е. обеспечивать решение задачи за допустимое машинное время или, в силу конечной скорости вычислений на компьютере, – за допустимое число действий.

Для большинства алгоритмов время решения задачи (объем вычислений) Q() возрастает при повышении точности, т.е. при уменьшении. Конечно, можно задать настолько малым, что время счета задачи станет недопустимо большим. Важно знать, что алгоритм дает принципиальную возможность получить решение задачи с любой точностью. Однако на практике величину выбирают, учитывая требование точности и возможность реализуемости алгоритма на данном компьютере. Для каждой задачи, алгоритма и машины есть свое характерное значение.

Естественно добиваться, чтобы число действий (и тем самым машинное время решения задачи) Q() было минимальным для данной задачи. Для любой задачи можно предложить много алгоритмов, дающих одинаковую по порядку (при 0) точность 0, но за разное число действий Q(). Среди этих эквивалентных по порядку точности алгоритмов надо выбрать тот, который дает решение с затратой наименьшего машинного времени (числа действий Q()). Такие алгоритмы будем называть оптимальными.

Остановимся еще на одном требовании, предъявляемом к вычислительному алгоритму, а именно – требовании отсутствия аварийного останова (авоста) компьютера в процессе вычислений. Следует иметь в виду, что компьютер оперирует с числами, имеющими конечное число значащих цифр и принадлежащих (по модулю) не всей числовой оси, а некоторому интервалу (М0,М), М00, М, где М0 – машинный нуль, М – машинная бесконечность. Если условие ММ в процессе вычислений нарушается, то происходит аварийный останов вследствие переполнения разрядной сетки, и вычисления прекращаются. Возможность авоста зависит как от алгоритма, так и от исходной задачи.

Если решение исходной задачи выражается через очень большие (очень малые) числа ММ (ММ0), то, как правило, путем изменения масштабов можно привести задачу к виду, содержащему только величины, принадлежащие (по модулю) заданному интервалу (М0,М). Часто возможность авоста может быть устранена путем изменения порядка действий. Поясним это на простом примере.

Пример 1. Пусть М=10р, М0=10-р, р=2n, n – целое число. Требуется вычислить произведение чисел 10p/2,10p/4,10-p/2,103p/4,10-3p/4.

1-й способ. Перенумеруем числа в порядке убывания: q1=103p/4, q2=10p/2, q3=10p/4, q4=10-p/2, q5=10 и образуем произведения Sk+1=Skqk+1, S1=q1. Тогда уже на первом шаге мы получим авост, т.к. S2=q1q2=105p/4M.

2-й способ. Перенумеруем числа в порядке возрастания: q1=10-3p/4, q2=10-p/2, q3=10p/4, q4=10, q5=103p/4. В этом случае мы получим на первом шаге S2 = q1q2 =10-5p/4M0, т.е. S2 – машинный нуль; нулю равны и все последующие произведения S3, S4, S5; таким образом, здесь происходит полная потеря точности.

3-й способ. Перемешаем эти числа, полагая, q1=10-3p/4, q2=10p/2, q3=103p/4, q4=10-p/2, q5=10p/4.

Тогда последовательно найдем: S2=q1q2=10-p/4, S3=S2q3=10p/2, S4=S3q4=100, S5=S4q5=10p/4, т.е. в процессе вычислений не появляются числа, большие 10p/2 и меньшие 10-p/4. Такой алгоритм является безавостным.

При каждом акте вычислений появляются погрешности округления. В зависимости от алгоритма эти погрешности округления могут либо нарастать, либо затухать. Если в процессе вычислений погрешности округления неограниченно нарастают, то такой алгоритм называют неустойчивым (вычислительно неустойчивым). Если же погрешности округления не накапливаются, то алгоритм называется устойчивым.

Пример 2. Пусть требуется найти yi (0i i0) по формуле yi+1=yi+d (i 0) при заданных y0, d. Предположим, что при вычислении yi внесена погрешность (например, погрешность округления), имеющая величину i, т.е. вместо точного значения yi получено приближенное значение y i = y i + i. Тогда вместо точного значения yi+1 получим приближенное значение промежуточном шаге, не увеличивается в процессе вычислений. Алгоритм устойчив.

Пример 3. Рассмотрим уравнение yi+1=qyi (i0, y0 и q заданы). Пусть, как и в примере 2, вместо yi получено значение y i = y i + i. Тогда вместо yi+1 получим приближенное значение y i +1 = q ( y i + i ) = y i +1 + q i. Таким образом, погрешность i+1= y i +1 y i +1, возникающая при вычислении yi+1, связана с погрешностью i уравнением i+1=qi, i=0,1,2,…. Следовательно, если q 1, то в процессе вычислений абсолютное значение погрешности будет возрастать (алгоритм неустойчив). Если же Неустойчивость обычно связывают со свойством экспоненциального нарастания ошибки округления. Если же погрешность округления нарастает по степенному закону при переходе от одной операции к другой («от шага к шагу»), то алгоритм считают условно устойчивым (устойчивым при некоторых ограничениях на объем вычислений и требуемую точность). Процесс вычислений можно трактовать так: при переходе от шага к шагу происходит искажение (за счет погрешностей округления) последних значащих цифр (от последних значащих цифр справа налево движется «волна погрешности округления»). Нам нужно обычно сохранить верными несколько первых значащих цифр (4-5 знаков), и поэтому вычисления должны быть закончены до того, как до них дойдет «волна погрешности округления». Если погрешность округления 0 нарастает от шага к шагу по экспоненциальному закону, то это приводит, как правило, к авосту на промежуточном этапе вычислений, если (как в примере 3) q 0 M.

Если М=10р, 0=10-k 0, то авост наступает при i0(p+k0)/lg q. Иначе обстоит дело при степенном росте погрешности округления. Пусть y i in0 (n1); тогда авост наступит при очевидного ограничения iМ=10р. Неравенство y i, где =10-k – заданная точность, ограничение на число уравнений ii0. Так, при k0=12, k=6 имеем i106/n, так что i103 при n=2.

Ясно, что можно указать такое большое n, что допустимое число уравнений i0 очень мало. Однако на практике обычно встречаются случаи небольшого n.

При решении любой задачи необходимо знать какие-то входные (исходные) данные – начальные, граничные значения искомой функции, коэффициенты или правую часть уравнения и др. Для каждой задачи ставятся одни и те же вопросы: существует ли решение задачи, является ли оно единственным и как зависит решение от входных данных? Возможны два случая. В первом случае задача поставлена корректно (задача корректна). Это значит, что 1) задача разрешима при любых допустимых входных данных; 2) имеется единственное решение; 3) решение задачи непрерывно зависит от входных данных (малому изменению входных данных соответствует малое изменение решения) – иными словами, задача устойчива. Во втором случае задача поставлена некорректно (задача некорректна). Такой вариант возникает, если, например, решение задачи неустойчиво относительно входных данных (малому изменению входных данных может соответствовать большое изменение решения).

Примером корректной задачи может служить задача интегрирования, а примером некорректной задачи – задача дифференцирования.

Пример 4. Задача интегрирования. Дана функция f(x); найти интеграл J= Заменим f на f и рассмотрим J = Ясно, что J max f ( x ), J, если f, т.е. J непрерывно зависит от f. Для вычисления интеграла J воспользуемся квадратурной формулой:

Повторяя рассуждения, приведенные выше, получим Таким образом, задача вычисления интеграла по квадратурной формуле корректна.

Пример 5. Задача дифференцирования. Задача дифференцирования функции u(x), заданной приближенно, является некорректной. В самом деле, пусть u (x)=u(x)+ u c = u u = 1 / N при N1/. Для погрешности производных u'= u '-u'=NcosN2x имеем u' c =N1/. Таким образом, малому изменению O() в С функции u(x) соответствует большое изменение O(1/) в С ее производной. Поэтому численное дифференцирование некорректно.

Чтобы найти приближенное значение производной по формуле разностной производной с некоторой точностью 0 при условии, что функция задана с погрешностью i ( i 0 ), необходимо выполнение условий согласования, 0 и шага h сетки, например, вида k (k=const0 не зависит от h, 0, причем шаг сетки ограничен как снизу, так и сверху. Таким образом, достижимая точность численного дифференцирования лимитируется точностью задания самой функции.

В данном курсе рассматриваются только корректные задачи и численные методы, ориентированные на использование компьютеров.

Численные методы дают приближенное решение задачи. Это значит, что вместо точного решения u (функции или функционала) некоторой задачи мы находим решение y другой задачи, близкое в некотором смысле к искомому. Как уже указывалось, основная идея всех методов – дискретизация или аппроксимация (замена, приближение) исходной задачи другой задачей, более удобной для решения на компьютере, причем решение аппроксимирующей задачи зависит от некоторых параметров, управляя которыми можно определить решение с требуемой точностью.

Например, в задаче численного интегрирования такими параметрами являются узлы и веса квадратурной формулы. Далее, решение дискретной задачи является элементом конечномерного пространства. Остановимся на этом подробнее.

Рассмотрим, например, дискретизацию пространства H={f(x)} функций f(x) непрерывного аргумента x[a,b]. На отрезке a x b введем конечное множество точек ={xi, i=0,1,…,N, x0=a, xN=b, xixi+1}, которое назовем сеткой. Точки xi будем называть узлами сетки. Множество без узлов x0 и xN будем обозначать. Если расстояние hi=xi-xi-1 между соседними узлами постоянно (не зависит от i), hi=h для всех i=1, 2,…, N, то сетку называют равномерной (с шагом h), в противном случае – неравномерной. Вместо функции f(x), определенной для всех x[a,b], будем рассматривать сеточную функцию yi=f(xi) целочисленного аргумента i (i=0, 1,…, N) или узла xi сетки, а H={f(x), x[a,b]} заменим конечномерным (размерности N+1) пространством HN+1={yi, 0iN} сеточных функций. Очевидно, что сеточную функцию yi=f(xi) можно рассматривать как вектор y=(y0, y1,…, yN).

Можно провести также дискретизацию и пространства функций f(x) многих переменных, когда x=(x1, x2,…, xp) – точка р-мерного евклидового пространства (р1). Так, на плоскости (x1, x2) можно ввести сетку ={xi=(i1h1, i2h2), i1, i2 =0, ± 1,±2,...} как множество точек (узлов) пересечения перпендикулярных прямых x1 1 = i1 h1, x 2 2 = i 2 h2, h1 0, h2 0, i1, i 2 = 0,±1,±2,..., где h1 и h2 – шаги сетки по направлениям x1 и x2 соответственно. Сетка, очевидно, равномерна по каждому из переменных в отдельности. Вместо функции f(x)=f(x1, x2) будем рассматривать сеточную функцию прямоугольнику (0x1l1, 0x2l2), так что h1=l1/N1, h2=l2/N2, то сетка имеет конечное число N=(N1+1)(N2+1) узлов, а пространство HN сеточных функций yi= y i1i2 является конечномерным.

Мы всюду рассматриваем только конечномерное пространство сеточных функций.

Заменяя пространство H={f(x)} функций непрерывного аргумента и исходную задачу пространством H сеточных функций и дискретной аппроксимацией исходной задачи, мы должны быть уверены, что будем лучше приближаться к решению исходной задачи при увеличении числа узлов. Оценка качества приближения и выбор способа аппроксимации – главная задача теории численных методов.

Основное содержание курса в той или иной степени связано с применением разностных методов для решения дифференциальных уравнений. Выделим два главных вопроса:

1) получение дискретной (разностной) аппроксимации дифференциальных уравнений и исследование получающихся при этом разностных уравнений;

2) решение разностных уравнений.

При получении дискретной аппроксимации (разностные схемы) важную роль играет общее требование, чтобы разностная схема как можно лучше приближала (моделировала) основные свойства исходного дифференциального уравнения. Такие разностные схемы можно получать, например, при помощи вариационных принципов и интегральных соотношений. Оценка точности разностной схемы сводится к изучению погрешности аппроксимации и устойчивости схемы.

Изучение устойчивости – центральный вопрос теории численных методов и ему уделяется большое внимание в данном курсе. Алгоритмы для сложных задач можно представить как последовательность (цепочку) простых алгоритмов (модулей). Поэтому многие принципиальные вопросы теории числовых методов можно выяснить на простых алгоритмах.

В первой главе рассматриваются одномерные (зависящие от одного целочисленного аргумента) разностные уравнения.

Вторая глава посвящена численному решению алгебраических и трансцендентных уравнений.

В третьей главе излагаются основы теории интерполирования.

Четвертая глава содержит основные методы численного интегрирования.

В пятой главе рассматривается численное решение систем линейных алгебраических уравнений.

Шестая глава дает основные сведения классификации, постановки и решения задач линейного программирования.

В этой главе изучаются сеточные функции целочисленного аргумента и разностные уравнения второго порядка. Излагается простейший математический аппарат для изучения сеточных функций и разностных операторов. Для решения разностных уравнений второго порядка применяется метод исключения, называемый методом прогонки.

Как уже упоминалось, в приближенных методах обычно функции непрерывного аргумента заменяются функциями дискретного аргумента – сеточными функциями. Сеточную функцию можно рассматривать как функцию целочисленного аргумента:

Для y(i) можно ввести операции, являющиеся дискретным (разностным) аналогом операций дифференцирования и интегрирования.

Аналогом первой производной являются разности первого порядка:

yi=yi+1-yi – правая разность;

yi=yi-yi-1 – левая разность;

(yi+ yi)= (yi+1-yi-1) – центральная разность;

следует заметить, что yi= yi+1.

Далее можно определить разности второго порядка:

2yi=(yi)=(yi+1-yi)=yi+2-2yi+1+yi, yi=(yi-yi-1)=(yi+1-yi)-(yi-yi-1)=yi+1-2yi+yi-1, Аналогично определяется разность m-го порядка: myi=(m-1yi), содержащая значения yi, yi+1,…,yi+m. Очевидно, что 1.1.1.2. Разностные аналоги формул дифференцирования произведения и интегрирования Пусть yi, vi – произвольные функции целочисленного аргумента. Тогда справедливы формулы:

которые проверяются непосредственно. Например, yivi+vi+1yi=yi(vi+1-vi)+vi+1(yi+1-yi)=yi+1vi+1-yivi=(yivi).

При выводе формулы для (yivi) достаточно учесть, что (yivi)=(yi-1vi-1).

Формулы (1), (2) представляют собой аналоги формулы дифференцирования произведения (y(x)v(x))'=yv'+vy'.

Аналогом формулы интегрирования по частям является формула суммирования по частям:

которую записывают также в виде Для вывода формулы (3) воспользуемся формулой (1). Поскольку yi= yi+1, из формулы (1) следует отсюда получаем Формулу суммирования по частям можно использовать для вычисления сумм.

vi+1=vi+(i+1)=v1+(2+3+…+(i+1))=(v1-1)+(i+1)(i+2)/2, vi=v1-1+i(i+1)/2. Выберем v1 из условия vN=0, т.е. v1=1-N(N+1)/2. Применяя формулу (3) и учитывая, что y0=0, vN=0, yi=1, находим так что SN=(N-1)N(N+1)/3. Отсюда следует, что Линейное уравнение относительно сеточной функции yi=y(i) (i=0, 1, 2,…) где ak(i) (k=0, 1, …, m), f(i) – заданные сеточные функции, a0(i) 0, am(i) 0, называется линейным разностным уравнением m-го порядка. Оно содержит m+1 значение функций y(i).

Пользуясь формулами для разностей yi, 2yi,…, m-1yi, можно выразить значения yi+1, yi+2,…, ym+1 через yi и указанные разности: yi+1=yi+yi, yi+2=2yi+2yi+1-yi=2yi+2yi+yi и т.д. В результате из (1) получим новую запись разностного уравнения m-го порядка:

(чем и объясняется термин «разностное уравнение»). Если коэффициенты a0, a1,…, am не зависят от i, a0 0, am 0, то (1) называется линейным разностным уравнением m-го порядка с постоянными коэффициентами.

При m=1 из (1) получаем разностное уравнение первого порядка при m=2 – разностное уравнение второго порядка Мы ограничимся изучением разностных уравнений первого и второго порядков.

Рассмотрим разностное уравнение первого порядка (3). Подставляя yi+1=yi+yi, получим Простейшими примерами разностных уравнений первого порядка могут служить формулы для вычисления членов арифметической прогрессии yi+1=yi+d и геометрической прогрессии yi+1=qyi.

Запишем уравнение (3) в виде где qi=-a0(i)/a1(i), i=f(i)/a1(i). Отсюда следует, что решение y(i) определено однозначно при ii0, если задано значение y(i0). Пусть при i=0 задано y0=y(0). Тогда можно определить y1, y2,…, yi,…. Последовательно исключая yi, yi-1,…, y1 по формуле (4), получим или Для уравнения с постоянным коэффициентом, когда qi=q из (5) получаем т.е. решение разностного уравнения (4) с постоянными коэффициентами.

Если в выражениях типа (1) или (2) знак равенства заменить знаками неравенства,,,, то получим разностные неравенства m-го порядка Пусть дано разностное неравенство первого порядка Не ограничивая общности, далее всегда считаем q0 (y0,, q, fi известны). Найдем его решение. Пусть vi – решение разностного уравнения Тогда справедлива оценка В самом деле, вычитая (8) из (7), находим Подставив в (9) явное выражение для vi получим решение неравенства (7).

1.1.2.4. Уравнение второго порядка с постоянными коэффициентами Рассмотрим разностное уравнение второго порядка коэффициенты которого не зависят от i. Если fi =0, то уравнение называется однородным. Его решение может быть найдено в явном виде.

Пусть y i – решение однородного уравнения (12), y i* – какое-либо решение неоднородного уравнения (11). Тогда их сумма yi= y i+ y i* также является решением неоднородного уравнения:

b( y i+1+ y i*+1 )-c( y i+ y i* )+a( y i-1+ y i*1 )=[b y i+1-c y i+a y i-1]+[b y i*+1 -c y i* +a y i*1 ]=fi.

Это свойство – следствие линейности уравнения (11); оно сохраняет силу для разностного уравнения (1) любого порядка. Очевидно, что если y i является решением однородного уравнения (12), то и c y i, где с – произвольная постоянная, также удовлетворяет этому уравнению.

Пусть y i(1) и y i( 2 ) – два решения уравнения (12). Они называются линейно независимыми, если равенство возможно только при с1=с2=0. Это эквивалентно требованию, что определитель системы отличен от нуля для всех i, m. В частности, Так же, как и в теории дифференциальных уравнений, можно ввести понятие общего решения разностного уравнения (12) и показать, что если решения y i(1), y i( 2 ) линейно независимы, то общее решение уравнения (12) имеет вид где c1 и c2 – произвольные постоянные. Общее решение неоднородного уравнения (11) можно представить в виде где y * – какое-либо (частное) решение уравнения (11). Для определения c1 и c2, как и в случае дифференциальных уравнений, надо задать дополнительные условия – начальные или краевые.

Общее решение уравнения (12) можно найти явно. Будем искать линейно независимые решения уравнения (12) в виде yi=qi, где q 0 – неизвестное пока число. После подстановки yk=qk в (12) получим квадратное уравнение bq2–cq+a=0, имеющее корни В зависимости от значений дискриминанта D=c2–4ab возможны три случая.

1) D=c2–4ab0. Корни q1 и q2 действительны и различны. Им соответствуют два решения = q1k, y k2) = q 2, которые линейно независимы, т.к. отличен от нуля определитель y k1) Заметим, что q1 0 и q2 0, иначе a=0, и уравнение (12) не является разностным уравнением второго порядка. Общее решение уравнения (12) имеет вид 2) D=c –4ab0. Квадратное уравнение имеет комплексно-сопряженные корни где i – мнимая единица. Эти корни удобно представить в виде Линейно независимыми решениями являются не только функции:

но и функции которые также линейно независимы в силу линейной независимости функций sink и cosk.

Общее решение имеет вид 3) D=c2 –4ab=0. Корни действительны и равны: q1=q2=c/(2b)=q0. Линейно независимыми являются решения Покажем, что y k2 ) есть решение уравнения (12):

общее решение имеет вид Рассмотрим примеры решения разностных уравнений второго порядка (11).

1. Найти общее решение уравнения Возможны три случая:

1) p1. Положим p=cos; тогда D=4(cos2-1)=-4sin20. Линейно независимые решения имеют 2) p1. Полагая p=ch, получим для q квадратное уравнение q2–2qch+1=0; его дискриминант равен D=4(ch2-1)=4sh2, а корни имеют вид q1,2=ch ± sh=e ±. Линейно независимыми решениями являются функции y k1) = chk, y k 2 ) = shk.

3) p=1. В этом случае q2 –2q+1=0, q1,2 =1, линейно независимые решения имеют вид Во всех трех случаях общее решение рассматриваемого однородного уравнения будет 2. Найти решение уравнения Дискриминант равен D=1+8=9, корнями будут q1,2=(1 ± 3)/2, q1=2, q2=-1. Общее решение имеет вид yk=c12k+c2(-1)k.

3. Найти общее решение уравнения Общее решение неоднородного уравнения есть сумма y k = y k + y k общего решения y k однородного уравнения и частного решения y k неоднородного уравнения. Найдем сначала общее решение однородного уравнения. Дискриминант равен D=1+24=250, и корни квадратного уравнения q2-q-6=0 равны q1=3, q2=-2, так что y k1) = 3 k, y k 2 ) = (2) k. Частное решение y k будем искать в виде y k = c 2 k, где c=const. Подставляя y k = c 2 k в (18), получим c(2k+1-2k-6*2k-1)=c2k-1(k+1, c=-1. Общее решение уравнения (18) имеет вид yk=c13k+c2(-2)k-2k.

1.1.2.6. Разностное уравнение второго порядка с переменными коэффициентами. Задача Рассмотрим теперь разностное уравнение с переменными коэффициентами Так как bi 0, то из (19) получаем следующее рекуррентное соотношение Выразим yi+1 и yi-1 через yi и разности первого и второго порядков. Тогда уравнение (19) перепишется в виде Решение разностного уравнения первого порядка зависит от произвольной постоянной и определяется однозначно, если задано одно дополнительное условие, например, y0=c0. Решение уравнения второго порядка определяется двумя произвольными постоянными и может быть найдено, если заданы два дополнительных условия. Если оба условия заданы в двух соседних точках, то это задача Коши. Если же два условия заданы в двух разных (но не соседних) точках, то получаем краевую задачу. Для нас основной интерес будут представлять краевые задачи. Введем обозначение Lyi=biyi+1-ciyi+aiyi-1 и сформулируем эти задачи более подробно.

Задача Коши: найти решение уравнения при дополнительных условиях Второе условие (22) можно записать иначе: y0=y1-y0=µ2-µ1= µ 1 и говорить, что в случае задачи Коши заданы в одной точке i=0 величины y0=µ1, y0= µ 1.

Краевая задача: найти решение уравнения Lyi=fi, i=1, 2,…N-1 при дополнительных условиях В граничных узлах i=0 и i=N можно задать не только значения функций, но и комбинации их с разностями, т.е. выражения 1 y 0 + 1 y 0 при i=0 и 2 y N + 2 y N при i=N. Такие условия можно записать в виде Если 1=2=0, то отсюда получаем условия первого рода; при 1=2=1 имеем условия второго рода Если 1,2 0,1, то (24) называют условиями третьего рода:

Кроме того, возможны краевые задачи с комбинацией этих краевых условий: при i=0 – условия одного типа, при i=N – условия другого типа.

Решение задачи Коши находится непосредственно из уравнения (21) по рекуррентной формуле (20) с учетом начальных данных y0=µ1, y1=µ2. Решение краевых задач находится более сложным методом – методом исключения – и будет изложено ниже.

Для уравнения с постоянными коэффициентами решение краевой задачи может быть найдено в явном виде.

Пример. Найти решение краевой задачи Однородное уравнение 2yi-1=yi-1-2yi+yi-1=0 имеет общее решение y i = c1 + c2 i. Частное решение yi* неоднородного уравнения 2yi-1=yi+1-2yi+yi-1=1 ищем в виде yi* =ci2. Подставляя это выражение в уравнение (27), находим 2y *1 =c((i+1)2-2i2+ +(i-1)2)=1, т.е. c=1/2, так что yi= y i + yi* = c1 + c2 i + i 2 / 2. Для определения c1 и c2 служат краевые условия при i=0, i=N:

y0=c1=0, yN=c2N+N2/2=0, c2=-N/2. Таким образом, yi=-iN/2+i2/2=-i(N-i)/2 есть решение задачи (27).

1.1.3. Решение разностных краевых задач для уравнений второго порядка 1.1.3.1. Решение разностных краевых задач методом прогонки aiyi-1-ciyi+biyi+1=-fi, ai 0, bi 0, i=1, 2,…, N-1, y0=1y1+µ1, yN=2yN-1+µ2 (1) представляет собой систему линейных алгебраических уравнений с трехдиагональной матрицей размера Вместо (1) можно написать В случае первой краевой задачи соответствующая матрица имеет размер Для решения краевой задачи (1) можно использовать следующий метод исключения, называемый методом прогонки. Предположим, что имеет место соотношение с неопределенными коэффициентами i+1 и i+1, и подставим yi-1=iyi+i в (1):

Сравнивая это тождество с (3), находим Используем краевое условие при i=0 для определения 1, 1. Из формул (1) и (3) для i= находим Зная 1 и 1 и переходя от i к i+1 в формулах (4) и (5), определим i и i для всех i=2, 3,…, N. Вычисления по формуле (3) ведутся путем перехода от i+1 к i (т.е. зная yi+1, находим yi), и для начала этих вычислений надо задать yN. Определим yN из краевого условия yN=2yN-1+µ2 и условия (3) при i=N-1: yN-1=NyN+N. Отсюда находим Соберем все формулы прогонки и запишем их в порядке применения Стрелки показывают направление счета: () от i к i+1, () - от i+1 к i.

Таким образом, краевая задача для уравнения второго порядка сведена к трем задачам Коши для уравнений первого порядка.

Формулы прогонки можно применять, если знаменатели дробей (8) и (10) не обращаются в нуль. Достаточными условиями этого являются неравенства причем одно из первых двух неравенств второй строки должно быть строгим. Покажем, что при условиях (11) знаменатели ci-aii и 1-N2 не обращаются в нуль и Предположим, что i 1 и покажем, что i +1 1 ; тогда отсюда и из условия Заметим, что если c i0 a i0 + bi0 хотя бы в одной точке i=i0, то i 1 для всех ii0 и в 1 N 2 1 N 2 1 2 0. Таким образом, при выполнении условий (11) задача (1) имеет единственное решение, которое мы находим по формулам прогонки (8) – (10).

Вычисления по формулам (8) – (10) ведутся на компьютере приближенно, с конечным числом значащих цифр. В результате погрешностей округления фактически находится не функция yi – решение задачи (1), а y i – решение той же задачи с возмущенными коэффициентами a i, b i, c i, 1, 2 и правыми частями f i, µ 1, µ 2. Возникает естественный вопрос: не происходит ли в ходе вычислений возрастание погрешности округления, что может привести как к потере точности, так и к невозможности продолжать вычисления из-за роста определяемых величин?

Примером может служить нахождение yi по формуле yi+1=qyi при q1. Поскольку yn=qny0, для любого y0 можно указать такое n0, при котором y n0 будет машинной бесконечностью. Фактически в силу погрешностей округления определяется не точное значение yi, а значение y i из уравнения y i +1 = q y i +, где – погрешность округления. Для погрешности yi= y i yi получим уравнение yi+1=qyi+ (i=0, 1,…, y0=). Из формулы yi=qi+(q1-1)/(q-1) следует, что погрешность yi при q1 экспоненциально растет с ростом i.

Вернемся к методу прогонки и покажем, что при i 1 погрешность yi не нарастает. В самом деле, из y i = i +1 y i +1 + i +1, yi=i+1yi+1+i+1 следует yi=i+1yi+1, yi i +1 yi +1 yi +1, так как i +1 1.

Если учесть, что в ходе вычислений возмущаются и коэффициенты i+1, i+1, то можно показать, что погрешность yi пропорциональна квадрату числа узлов N: max yi 0 N 2, где 0 – погрешность округления. Отсюда видна связь между требуемой точностью решения задачи, числом N уравнений и числом значащих цифр компьютера, поскольку 0N2.

Рассмотренный выше метод прогонки (8) – (10), при котором определение yi производится последовательно справа налево, называют правой прогонкой. Аналогично определяются формулы левой прогонки:

В самом деле, предполагая, что yi+1=i+1yi+i+1 и исключая из (1) yi+1, получим -fi=aiyif + bi i + получим (13) и (14). Значение y0 находим из условия y0=1y1+µ1 и формулы y0=1y1+1. Из неравенств ci bi i +1 ci bi i +1 ai + bi (1 i +1 ), 1 11 1 1 1 следует, что условия (11) гарантируют применимость формул левой прогонки и их вычислительную устойчивость, т.к.

i 1 (i=1, 2,…, N).

Комбинация левой и правой прогонок дает метод встречных прогонок. В этом методе в области 0 i i0 + 1 по формулам (8), (9) вычисляются прогоночные коэффициенты i, i, а в области i0 i N по формулам (13), (14) находятся i и i. При i=i0 производится сопряжение решений в форме (10) и (15).

единицы, и, следовательно, 1 i0 +1 i0 +1 0. Зная yi0, можно по формуле (10) найти все yi при ii0, а по формуле (15) – значения yi при ii0. Вычисления при ii0 и ii0 проводятся автономно (имеет место распараллеливание вычислений). Метод встречных прогонок особенно удобен, если, например, требуется найти yi лишь в одном узле i=i0.

Модуль 2. Решение уравнений и задачи интерполяции 2.2. Численное решение алгебраических и трансцендентных уравнений Задача численного решения уравнения распадается на две:

1) задача отделения корней – нахождение областей, которым принадлежат корни уравнений;

2) задача численного нахождения приближенных значений корня (с заданной степенью точности).

Существует несколько методов отделения корней уравнения.

1. Главный метод – знание свойств функций, входящих в уравнение. Например, в выражении нет необходимости рассматривать знаменатель, т.к. он никогда не обращается в нуль.

2. Графические методы отделения корня а) На вещественной оси (построение таблицы значений функции). Пусть дана функция Т.к. ось бесконечна, необходимо построение провести в два этапа. На первом разбивают сегмент [-1,1] на сколь угодно малые части и получают значения функции в точках разбиения. На втором этапе осуществляют замену переменной t = 1 / x, что приводит к следующему преобразованию интервалов: [1,+ ) [1,0) и (-,-1] (0,-1], т.е. снова получаем сегмент [возвращаясь к первому этапу.

б) Функция комплексной переменной P ( z ) = 0. Поскольку z = x + iy, выделяют действительную и мнимую части функции P (z ) : P ( z ) = Q( x, y ) + iL( x, y ), где Q и L вещественны. Комплексное число равно нулю тогда и только тогда, когда Q = 0 и L = 0, т.е.

задача свелась к поиску корней вещественных функций. Эти кривые строятся в декартовой системе координат, где выделяются области пересечения кривых Q( x, y ) = 0 и L( x, y ) = 0, как показано на рис.2.1.

3. Метод малого параметра Пусть P ( z ) = 0 можно представить в виде и пусть значения корней Q(z ) известны. Тогда корни P (z ) должны находиться вблизи корней Q(z ).

Обозначив Q( x) = x 2 5 x + 6, ( x) = 0,001x 3, получим (как следует из анализа рисунка 2.2) небольшой сдвиг корней.

2.2.2. Вычисление значений корня с заданной точностью. Метод итераций Будем считать, что первая задача (задача отделения корней) решена, т.е. выделена область, в которой P( z ) = 0. Требуется найти в ней корень с любой точностью. Уравнение преобразуем к виду например, с помощью следующего приема:

В выделенной области назначим приближение z 0 – нулевое приближение корня.

Следующие приближения корня находим так:

Предположим, что последовательность {z n }n =0 сходится к некоторому z *, и что функция (z ) непрерывна. Перейдем в (2) к пределу:

Если указанный итерационный процесс сходится, то предел последовательности является решением исходного уравнения.

При рассмотрении задачи в комплексной плоскости областью отделения корня является круг радиуса, а z o – центром этого круга.

Теорема. Пусть уравнение z = (z ) и радиус области отделения корня удовлетворяют следующим условиям:

1) для любых двух точек z ' и z ' ', находящихся в области | z z 0 |, имеет место неравенство где q – вещественное число из интервала (0,1);

2) имеет место неравенство Тогда последовательность приближенных значений корня {z n } сходится, и предел последовательности принадлежит заданной области отделения корня. Кроме того, скорость сходимости определяется следующим неравенством:

Доказательство Формально доказательство сводится к доказательству справедливости следующей формулы:

Проведем доказательство по индукции.

1. База индукции. Покажем, что формула справедлива при k = 1 :

2. Индукционный шаг. Пусть формула верна для k = n. Докажем, что она верна для k = n + 1, т.е. | z n +1 z n | mq n. Из справедливости формул для k = 1,2,..., n следует, что все {z k }n =1 находятся в круге выделения корня. Докажем это для любого k, например, для k = n :

Итак, любая точка z k, k = 1,2,..., n,не выходит из круга выделения корня. Рассмотрим Индукция закончена. Доказали, что неравенство | z k +1 z k | mq k справедливо при любых достаточный признаки Коши существования предела: 0N : n N, p | z n + p z n |, т.е.

последовательность, сходящаяся в себе, сходится. Оценим разность элементы последовательности принадлежат кругу | z z 0 |, то предел также лежит внутри этого круга. Докажем справедливость формулы скорости сходимости:

Покажем, что уравнение имеет единственное решение в круге радиуса.

Проведем доказательство от противного. Пусть, кроме решения z * существует решение Итак, решение единственно.

Обсудим условия теоремы.

Это условие называется условием Липшица. Оно является более широким, чем условие дифференцируемости функций, т.е. функции, имеющие производную, входят в класс функций, удовлетворяющих условию Липшица. Если функция дифференцируема и ее производная q, то она удовлетворяет условию Липшица. Действительно, применяя формулу Тейлора, можно записать или, переходя к модулю в левой и правой частях, и, обозначая максимум модуля производной через q, получаем условие Липшица.

Качественно процесс нахождения корня методом итераций продемонстрирован на следующих рисунках 2.3 и 2.4, на которых представлены функции, имеющие соответственно положительное и отрицательное значения производных.

При ' ( x) 0 последовательность x 0, x1,... монотонно сходится к корню x *, а при ' ( x) 0 итерационный процесс "закручивается" вокруг корня x *. Корень находится между двумя соседними значениями x k, x k +1.

На рисунке 2.5 продемонстрировано, каким образом сказывается невыполнение условия Липшица.

Обсудим второе условие теоремы. Оно говорит о том, что разность | ( x 0 ) x 0 | не может быть сколь угодно велика: она ограничена величиной (1 q ). Скорость сходимости существенно зависит от величины q, что иллюстрируется следующими рисунками.

При q 0 итерационный процесс сходится к значению корня x * очень быстро, при q – медленно.

Рассмотрим итерационный метод для решения системы k уравнений с k неизвестными:

Преобразуем эту систему к виду, удобному для использования итерационного метода:

Выбрав начальное приближение ( 1( 0 ), 2 0 ),..., k( 0 ) ), первое приближение будем искать в соответствии с выражением Аналогично получаем следующие приближения.

Покажем, что, используя понятие функционального метрического пространства, можно данную задачу свести к задаче, рассмотренной в предыдущем разделе.

Пусть R – полное метрическое пространство, каждый элемент которого x задается упорядоченным набором k чисел (действительных или комплексных) x( 1, 2,..., k ). Введем в x' = { 1, 2,..., k }, x' ' = { 1, 2,..., k }, пространства R Эта метрика хороша тем, что дает максимальную "невязку" между левой и правой частями уравнения.

Введем вектор-функцию (x), являющуюся элементом пространства R. Координаты этой функции определятся следующим образом:

Используя введенное обозначение в метрическом пространстве, систему уравнений (4) можно переписать в следующем виде:

Зададим нулевое приближение x 0 = { 1( 0 ), 2 0),..., k( 0 ) }, а также число 0.

Теорема. Пусть уравнение (7), нулевое приближение x 0 и удовлетворяют следующим условиям:

1) для любых x', x' ', принадлежащих области отделения корня радиуса, справедливо 2) имеет место неравенство m /(1 q ), где m = ( x 0, ( x 0 )).

Тогда итерационный процесс вида x n = ( x n 1 ) сходится, и lim{x n } является единственным корнем уравнения (7) в заданном шаре. Обозначая этот предел через x*, можно утверждать, что скорость сходимости итерационного процесса определяется неравенством Доказательство этой теоремы в точности повторяет доказательство предыдущей с заменой Пусть R – полное метрическое пространство и пусть для всех элементов этого пространства определен оператор А "в себя" (результат действия этого оператора – отображение элементов в элементы того же пространства). Тогда говорят, что оператор А осуществляет сжатое отображение, если для любых двух элементов x', x'' этого пространства и любого действительного числа 0q1 имеет место неравенство т.е. образы элементов ближе, чем их прообразы. В таких случаях говорят, что оператор А сжимает.

Теорема. Пусть в полном метрическом пространстве R оператор А осуществляет сжатие отображения "в себя". Тогда оператор А имеет единственную неподвижную точку, т.е. уравнение Ax=x имеет единственное решение, которое может быть получено как предел последовательности итераций вида x n = Ax n 1 (Точка является неподвижной для оператора, если он переводит ее саму в себя).

Покажем, что последовательность значений xn }n = 0, полученная итерированием, сходится в себе, т.е. ( xn, xm ) 0. Будем считать nm и запишем следующую последовательность неравенств:

Перемножив эти неравенства, получим Оценим ( xn m, x0 ), применив n-m раз правило треугольника:

Окончательно получаем т.е. при nm критерий Коши доказан: ( xn, xm ) 0. В силу полноты пространства R (для любой последовательности в пространстве R, сходящейся в себе, найдется предельный элемент, принадлежащий этому пространству) существует такой элемент x*, что lim x n = x *. Используя то обстоятельство, что оператор А – сжимающий, получим и, следовательно, ( Axn, Axm ) n, m 0, т.е. существует переходя в последнем равенстве к пределу, получаем Ax* = x, т.е. x* – решение уравнения, а значит – неподвижная точка оператора. Покажем, что эта точка единственная. Проведем доказательство от противного. Предположим, что существует еще одна неподвижная точка x' x* и Ax’=x’. Поскольку ( x*, x' ) = ( Ax*, Ax' ) q ( x*, x' ), а q1, то получили противоречие, т.е.

x’ не может быть неподвижной точкой.

2.2.5. Об одном принципе нахождения сходящихся итерационных процессов Пусть имеется уравнение f ( x) = 0, где x – действительная переменная и пусть на [a,b] отделен единственный корень x* этого уравнения. Пусть на этом сегменте задана некоторая непрерывная функция (x). Тогда уравнение вида x = x ( x) f ( x) также имеет корень x*.

Принцип получения сходящихся итерационных процессов состоит в следующем. Нужно уметь так подобрать непрерывную функцию (x), чтобы получившееся уравнение x = (x), где ( x) = x ( x), давало сходящийся итерационный процесс.

Данный метод является одним из методов, реализующих принцип получения сходящегося итерационного процесса. Пусть единственный корень x* уравнения f ( x) = 0 отделен на [a,b].

Предположим, что f (x) изменяется на [a,b] монотонно.

Заменим кривую y = f (x) хордой, проходящей через точки (a, f (a )) и (b, f (b)). В качестве первого приближения корня уравнения f ( x) = 0 возьмем точку пересечения этой хорды с осью x. Запишем уравнение этой хорды:

откуда получаем Подставляя в последнем выражении x = x1, y = 0, получаем Полагая теперь x 0 = a и учитывая, что f ( x i ) 0, f (b) 0, имеем f (a) 0, f (b) 0, f ' ( x) 0, f ' ' ( x) 0. Этим знакам соответствует чертеж (рис. 2.8). Для сходимости последовательности {x n }, значения элементов которой даются соотношением (8), важно, что все эти значения ограничены по величине и не превосходят b. Т.к.

корнем уравнения корнем уравнения f ( x) = 0. При других соотношениях знаков f (a ), f (b), f ' ( x), f ' ' ( x) доказательство аналогично.

Оценим разность между x n (приближенным значением корня) и истинным значением x *, полагая при этом, что f ' ( x) сохраняет постоянный знак на [a,b]. По формуле Лагранжа Формула тем точнее, чем меньше сегмент [a,b] отделения корня.

Из геометрии задачи вытекает, что первое приближение значения корня x1 делит сегмент [a,b] в соответствии со следующим соотношением:

в силу чего метод хорд часто называют методом пропорциональных частей. Если метод хорд "угрубить" и делить отрезок не на пропорциональные, а на две равные части, то получим метод нахождения корня делением сегмента пополам. При этом каждый раз после деления в качестве рабочей части выбирается та ее половина, на границах которой f(x) имеет противоположные знаки.

Теоретическим основанием для сходимости этого метода служит лемма о вложенных интервалах.

Каждый интервал содержится в другом, и при достаточно большом числе делений их длины стремятся к нулю. Тогда найдется только одна точка, которая принадлежит всем интервалам.

Пусть функция f(x) имеет на [a,b] единственный корень, и значения f(a), f(b) – противоположных знаков, существуют непрерывные f'(x), f''(x), которые сохраняют знак на [a,b].

Пусть некоторое значение x 0 (a, b). Заменим f(x) некоторой линейной функцией, используя формулу Лагранжа:

Поскольку значение неизвестно, выберем в качестве точку x0:

Исходя из последнего соотношения, интересующее нас уравнение f(x)=0 заменим уравнением f(x0)+f'(x0)(x-x0)=0, корень которого примем за первое приближение значения корня уравнения f(x)=0:

Обобщая уравнение (10), получаем следующий итерационный процесс:

С другой стороны, уравнение (9) является уравнением касательной к кривой в точке x0. На каждом шаге итерационного процесса функция f(x) заменяется касательной к этой функции, проведенной в точке предыдущего приближенного значения корня. Из геометрии задачи вытекает, что первую касательную удобно проводить с того конца сегмента, в котором выполняется условие Теорема. Если функция f(x) имеет единственный корень на [a,b], непрерывные f'(x), f''(x), которые не меняют знака на этом сегменте, то если начинать итерационный процесс со значения x 0 [a, b], для которого выполняется условие f ( x 0 ) f ' ' ( x 0 ) 0, то итерационный процесс монотонно сходится к некоторому значению корня x*.

Рассмотрим упрощенный метод Ньютона. Он заключается в том, что итерационный процесс строится на основе следующей формулы:

т.е. на каждом шаге используется одно и то же значение производной в начальной точке x0, что упрощает вычисления, но несколько уменьшает скорость сходимости итерационного процесса.

Пусть задан алгебраический полином n-й степени с действительными коэффициентами Требуется определить значение этого полинома в точке x0. Подсчитаем число операций, необходимых для решения этой задачи. Операций умножения: n+(n-1)+(n-2)+…+1=n(n+1)/2;

операций сложения: n. Нельзя ли предложить метод, сокращающий число операций?

Рациональный процесс подсчета значения многочлена основан на теореме Безу.

Теорема. Остаток от деления многочлена Pn (x) на двучлен (x-x0) равен значению многочлена в точке x0.

Доказательство Запишем результат деления Pn (x) на ( x x 0 ) в виде суммы остатка от деления R и многочлена (n-1)-й степени Q n1 ( x), т.е.

Положим в этом выражении x=x0:

Подставив этот результат в (14), получим Выразим коэффициенты многочлена Qn-1 через коэффициенты Pn.

Теорема. Два многочлена тождественно равны тогда и только тогда, когда их коэффициенты при одинаковых степенях x совпадают.

Преобразование коэффициентов удобно представить в виде так называемой схемы Горнера (таблица 1).

В соответствии с теоремой Безу bn = R = Pn ( x 0 ). При этом выполнено n действий умножения и n действий сложения.

2.2.9. Метод Лобачевского нахождения корней алгебраических многочленов Главное достоинство этого метода состоит в том, что он не требует знания о приближенных значениях корней. Он применяется в тех случаях, когда многочлен имеет различные действительные корни.

Метод реализуется в два этапа. Если корни многочлена удовлетворяют неравенству то приближенные значения корней выражаются через коэффициенты многочлена a 0 x n + a1 x n 1 +... + a n по обобщенной теореме Виета:

Из (17) с учетом (16) последовательно получаем:

Применяя формулу (18), получаем x1 91; x 2 10; x 3 1,1.

Если соотношения (16) не выполняются, то необходимо выполнить предварительный этап, называемый процессом квадрирования и суть которого состоит в следующем.

Запишем разложение многочлена на сомножители Запишем многочлен, корни которого отличаются от корней данного многочлена знаками:

Перемножим многочлены (19), (20):

Сделаем замену переменных x 2 = z. Получим многочлен n-й степени, корни которого равны корням в квадрате исходного многочлена, взятых со знаком "минус", т.е. x i2 }. Основная идея процесса квадрирования в том, что если корни различны, то разница по модулю при квадрировании существенно возрастает.

Выразим коэффициенты многочлена, полученного в результате квадрирования через коэффициенты исходного многочлена. Итак, пусть задан многочлен Домножим последнее соотношение на (-1)n:

Перемножая (21) и (22), получаем:

Сделаем замену переменной x=-x2:

Домножим получившееся выражение на (-1)n:

Правило получения коэффициентов после квадрирования: коэффициент bk при xn-k равен bk = a k 2a k 1 a k +1 + 2a k 2 a k + 2 +... до тех пор, пока не будет достигнут коэффициент a 0 или Процесс квадрирования можно повторить сколь угодно раз. Каков же критерий останова?

Пусть многочлены являются результатами квадрирования, т.е. (24) получается из (23) в результате очередного квадрирования. Пусть корни многочлена (23) уже настолько по модулю отличаются друг от друга, что можно применить (18), т.е.

т.е.

Поскольку x i( 2 ) = ( x i(1) ) 2, i = 1,2,..., n, то c i / c i 1 bi2 / bi21. Итак, с учетом того, что c 0 = b02, для каждого i получаем:

Следовательно последовательность процессов квадрирования следует заканчивать тогда, когда соотношение (25) выполняется с заданной степенью точности. Между корнями {x i } существует простая связь:

Пусть на некотором сегменте [a,b] вещественной оси заданы точки {x i }i =1, причем x1=a;

xm=b, и в этих точках заданы некоторые действительные значения { f ( x i )}i =1. Требуется найти такую непрерывную на [a,b] функцию (x), которая удовлетворяла бы следующим условиям:

(xi)=f(xi), i=1, 2,…,m. Задача нахождения функции (x), т.е. задача нахождения значений функции между заданными точками и есть задача интерполирования. При этом функция (x) называется интерполирующей (интерполяционной), а точки {x i }i =1 – узлами интерполяции.

Интерполяция применяется во многих задачах, связанных с вычислениями. Укажем некоторые из этих задач.

Обработка результатов физического эксперимента – построение приближенных формул для характерных величин по табличным данным, полученным экспериментально.

Построение приближенных формул по данным вычислительного эксперимента. Здесь возникают нестандартные задачи интерполяции, т.к. обычно пишутся формулы возможно более простой структуры.

Субтабулирование, т.е. сгущение таблиц. Применяется в тех случаях, когда непосредственное вычисление функции затруднено или когда имеется мало экспериментальных данных. В машину вводится наибольшая таблица, а нужные при расчетах значения функции находятся по мере необходимости по интерполяционной формуле.

Интерполяция применяется также в задаче обратного интерполирования: задана таблица yi=y(xi); найти xi как функцию от yi. Примером обратного интерполирования может служить задача о нахождении корней уравнения.

Интерполяционные формулы используются также при вычислении интегралов, при написании разностных аппроксимаций для дифференциальных уравнений на основе интегральных тождеств.

Пусть R – линейное пространство непрерывных действительных функций {f(x)} на [a,b].

Пусть конечная или счетная система функций {j(x)} R такова, что любой конечный набор из этих функций линейно независим. Рассмотрим функции j ( x) j = 0. Любое выражение вида A(x)=a00(x)+a11(x)+…+ann(x), где {aj} – действительные числа, называется "обобщенным" полиномом по системе функций j ( x) j = 0. Пусть на [a,b] заданы n+1 точка {x i }i = 0, и пусть в этих точках заданы значения f(xi), i=0, 1,…, n. Требуется построить "обобщенный" многочлен А(х) по системе функций j ( x) Определение. Система функций j ( x) на [a,b], если любой полином А(х) по этой системе функций имеет на сегменте [a,b] не более n нулей, в предположении, что хотя бы один из коэффициентов полинома отличен от нуля.

Теорема. Необходимое и достаточное условие того, чтобы существовал обобщенный интерполяционный полином по заданной системе функций j ( x) точках заданных на [a,b], и при любых значениях f(xi)=i, заключается в том, чтобы единственный.

Утверждение теоремы эквивалентно следующему утверждению: каковы бы ни были числа {x i }i =0 и каковы бы ни были числа i, система уравнений вида с неизвестными a0, a1,…, an должна иметь решение. Последняя задача эквивалентна тому, что главный определитель этой системы должен быть отличен от нуля при любых различных {x i }i = 0 на [a,b].

Покажем, что необходимое и достаточное условие того, чтобы выполнялось (1) заключается в следующем: система функций j ( x) Тогда между столбцами определителя существует линейная зависимость, т.е. найдутся числа Последнее эквивалентно тому, что существует полином, который обращается в 0 в n+ точках. Поскольку Т-система имеет n нулей, то получили противоречие, которое и доказывает справедливость выполнения соотношения (1).

противное. Тогда найдутся n+1 различных точек {x i }i = 0 на [a,b] таких, что некоторый полином система уравнений Но это однородная система уравнений, и она имеет отличные от нуля решения {c i }i = тогда и только тогда, когда главный определитель приведенной системы уравнений отличен от нуля. Поскольку этим определителем является определитель (1), то опять пришли к противоречию. Предположение не подтвердилось, поэтому j ( x) Итак, интерполяционный полином существует. Единственность существующего полинома вытекает из того, что система уравнений вида с неизвестными {ak} может иметь только одно решение, т.к. главный определитель этой системы отличен от нуля, и система является определенной.

система на всей вещественной оси.

доказательство сводится к доказательству следующего факта:

Получившийся определитель является хорошо известным в линейной алгебре определителем Вандермонда.

Из предыдущей теоремы вытекает, что обобщенный интерполяционный полином A(x)= При решении задачи интерполяции значения функции f(xi)=i достаточно произвольны.

Гораздо более важным является расположение узлов интерполяции {x i }i =1. Поэтому преобразуем k следующим образом. Разложим определитель k по элементам столбца 0,…,n:

j kj, где kj – алгебраические дополнения соответствующих элементов (с точностью до знака). Тогда выражение для A(x) может быть преобразовано следующим образом:

Существенная особенность многочленов Фj(x) состоит в том, что коэффициенты этих многочленов не зависят от значений f(xi)=i, а зависят только от расположения точек {x i }i = 0 на [a,b]. Многочлены Фj(x) носят название фундаментальных многочленов для заданной системы точек. Поскольку (что достаточно просто показать) дальнейшем будет широко использоваться.

Пусть i ( x) = x i, i=0,1,…,n. Требуется построить алгебраический интерполяционный j ( x) = Из данного свойства Фj(xi) следует, что можно Фj(xi) представить в следующем виде:

j ( x) = a. Воспользовавшись равенством Фj(xj)=1, определим значение коэффициента a:

которое представляет собой формулу интерполяционного полинома Лагранжа.

Если о функции известно только то, что она непрерывна, то никаких оценок интерполяции сделать нельзя. Предположим, что функция f(x), значения которой заданы в точках {x i }i = 0 на [a,b] непрерывно дифференцируема, и при этих условиях на функцию выведем формулу остаточного члена Rn(x)=f(x)-Ln(x), где Ln(x) – интерполяционный полином Лагранжа по системе функций. Введем в рассмотрение функцию, заданную на [a,b]:

где K – некоторая константа, значение которой требуется определить.

Найдем R(x) в некоторой фиксированной точке x xj, j=0,1,…,n, и подберем K таким образом, чтобы в этой точке (z) обращалась в ноль, т.е.

При полученном значении K функция (z) обращается в ноль не менее, чем в n+ различных точках: x, {x i }i = 0 ; тогда '(z) имеет не менее (n+1) действительных корней (нулей);

''(z) – не менее n нулей и т.д., (n+1)(z) – не менее одного. Пусть – действительный корень (n+1)(z), т.е. (n+1)()=0. Из формулы для (z) вытекает, что в любой точке z выполняется соотношений Rn(x)=f(x)-Ln(x), т+1(x)=(x-x0)(x-x1)…(x-xn), приводит к формуле остаточного члена полинома Лагранжа члена в формуле Лагранжа имеем следующую оценку:

Представляют интерес ответы на следующие вопросы: каково влияние выбора корней в обеспечивалось как можно меньшее значение max n+1 ( x) ? Ответ на эти вопросы следует искать, изучая свойства полиномов Чебышева. Полиномы Чебышева задаются следующим соотношением:

Tn(x)=cos(narccosx). Получим рекуррентное соотношение для вычисления значений полиномов Чебышева, для чего проведем следующие расчеты:

T0(x)=1; T1(x)=cos(arccosx)=x; T2(x)=cos(2arccosx)=2cos2(arccosx)-1=2x2-1.

Обозначая =arccosx (или x=cos), имеем cos(n-1)+cos(n+1)=2coscosn cos(n+1)=2coscosn-cos(n-1), или Найдем корни многочлена Tn(x) и его производной T'n(x). В принятых обозначениях имеем:

Tn(x)=cos(narccos(cos))=cosn; cosn=0; k=(2k+1)/(2n); xk=cos[(2k+1)/(2n)], k=0,1,…,n-1.

T'n(x)=nsin(narccosx)/ 1 x 2 ; sin(arccosx)=0; xj=cos(j/n), j=1,2,…,n-1.

Итак, все n корней многочлена Чебышева Tn(x) расположены на сегменте [-1,1];

экстремальные значения многочлена Tn[cos(j/n)]=cos(j)=(-1)j, j=1,2,…,n-1; на концах сегмента Tn(1)=1, Tn(-1)=(-1)т. Поэтому многочлен Чебышева n+1 раз достигает на [-1,1] экстремальное значение (-1)i с последовательным чередованием знаков.

Возьмем в качестве многочлена n+1(x) на [-1,1] следующий:

Анализ формулы (3) приводит к выводу, что старший коэффициент многочлена Tn(x) равен 2n-1. Тогда многочлен n+1(x) имеет единичный старший коэффициент, т.е. n+1(x) на [-1,1] уклоняется от нуля не более, чем на 1/2n.

Несложно доказать [1], что никакой другой многочлен Pn+1(x) с единичным старшим коэффициентом не уклоняется от нуля на [-1,1] менее, чем на 1/2n. Таким образом, среди всех многочленов n+1(x) наименее уклоняется от нуля многочлен 1/2nTn+1(x), который на сегменте [не превосходит величины 1/2n.

Итак, если в качестве узлов интерполяции выбрать корни многочлена Чебышева, то остаточный член формулы Лагранжа принимает следующий вид:

Разделенными разностями первого порядка называются следующие величины:

Разделенные разности второго порядка суть Тогда по индукции разделенная разность (k+1)-го порядка есть Свойства разделенных разностей:

1) для разделенных разностей k-го порядка имеет место формула 2) разделенная разность k-го порядка f[xj, xj+1,…, xj+k]=Fk(f) есть линейный функционал, т.е.

Fk[f(x) ± g(x)]=Fk[f(x)] ± Fk[g(x)], Fk[af(x)]=aFk[f(x)];

3) разделенная разность есть симметричная функция своих аргументов, т.е. аргументы можно переставлять, например, f[xj, xj+1,…,xj+k]= f[xj+1, xj,…,xj+k];

4) разделенные разности k-го порядка от функции xn есть однородные многочлены своих аргументов порядка (n-k), разделенные разности n-го порядка тождественно равны 1, а выше nго порядка равны 0;

5) учитывая, что алгебраический многочлен есть сумма степенных функций, получаем, что для любого алгебраического многочлена степени n разделенные разности n-го порядка равны const, а разделенные разности (n+1)-го порядка равны 0.

Рассматривая преобразование Ln(x)=L0(x)+[L1(x)-L0(x)]+[L2(x)-L1(x)]+…+[Ln(x)-Ln-1(x)], где Lk(x)-Lkx)=A(x-x0)(x-x1)…(x-xk-1), определим значение старшего коэффициента A, положив для этого x=xk:

Интерполяционная формула Ньютона имеет следующий вид:

Hn(x) Ln(x)=f(x0)+(x-x0)f[x0, x1]+(x-x0)(x-x1)f[x0, x1, x2]+ +…+(x-x0)(x-x1)…(x-xk)f[x0, x1,…xk+1]+…+(x-x0)(x-x1)…(x-xn-1)f[x0, x1,…xn].

Эта формула очень удобна, т.к. при добавлении новых точек интерполирования надо лишь добавлять новые слагаемые, не меняя старой записи. Используя тот факт, что разделенные разности – симметричные функции своих аргументов, новые узлы интерполирования можно брать в любом порядке, в том числе и в промежутках между старыми. Особенно удобна формула Ньютона при составлении таблиц.

В теории интерполирования можно выделить две основные задачи. Первую назовем "задачей приближения функции в точке". Для поиска решения этой задачи характерно стремление значение функции в некоторой фиксированной точке x[a,b]. Такая задача возникает при вычислении значения функции по таблице, когда значение x не совпадает с узлом таблицы.

Вторая задача состоит в "равномерном приближении функции на сегменте". При решении этой задачи стремятся получить возможно меньшее по модулю максимальное уклонение функции от интерполяционного полинома на всем сегменте [a,b]. При решении этой задачи большую роль играют оценки остаточных членов интерполяционных формул.

Прежде чем воспользоваться интерполяционной формулой, необходимо ответить на следующие вопросы.

1) Какие следует выбрать узлы?

В качестве узлов лучше всего брать корни многочлена Чебышева. Этот подход справедлив для равномерного приближения на отрезке. Если речь идет о таблицах, в подавляющем большинстве случаев выбирают равномерное распределение узлов.

2)Какой выбирается класс функций для интерполирования?

Чаще всего используются следующие системы функций:

системы функций переходят сами в себя при замене переменной x на x+a, т.е. эти системы функций не зависят от начала отсчета. Кроме того, система степенных функций переходит сама в себя и при замене переменной x на ax, т.е. она не зависит от масштаба.

3)Какова желаемая точность результатов?

Точность выбирается исходя из задачи. Вычислительная практика показывает, что вопрос о необходимой точности решения надо рассматривать не только перед вычислительным процессом, но и в ходе его, особенно на том этапе, когда полученные результаты преобразуются к виду, поставленному алгоритмистом.

4)Каким критерием согласия следует руководствоваться?

Классический критерий согласия, который используется в теории интерполирования следующий: требование точного совпадения интерполяционного многочлена со значениями функции в заданных точках. Если же рассматривать интерполирование более широко (например, использование интерполяционных формул при численном интегрировании), то можно использовать и другие критерии согласия: Приведем три таких критерия:

• минимизация суммы квадратов уклонений от значений функции в заданных точках, • минимизация уклонения интерполяционного полинома от функции на всем сегменте • совпадения в заданных точках значений интерполяционной функции не только со значениями функции, но и совпадение в этих точках значений их производных (сплайн-интерполяция).

Рассмотрим случай кусочно-полиномиальной интерполяции, когда между любыми соседними узлами интерполяции строится кубический полином (кубическая сплайнинтерполяция). Коэффициенты полинома на каждом интервале определяются из условий сопряжения в узлах:

Кроме того, на границе при x=x0 и x=xn ставятся условия Будем искать кубический полином в виде f(x)=ai+bi(x-xi-1)+ci(x-xi-1)2+di(x-xi-1)3, x[xi-1, xi]. (3) Из условия fi=yi имеем f(xi-1)=ai=yi-1, f(xi)=ai+bihi+cih i2 +dih 3 =yi, hi=xi-xi-1, i=1, 2,…, n-1. (4) Вычислим производные и потребуем их непрерывности при x=xi. Это требование после несложных преобразований приводит к следующим соотношениям:

bi+1=bi+2cihi+3dih i2, ci+1=ci+3dihi, i=1, 2,…, n-1. (5) Общее число неизвестных коэффициентов, очевидно, равно 4n, число уравнений (4), (5) равно 4n-2. Недостающие два уравнения получаем из условий (2) при x=x0 и x=xn:

Выражая из (5) di=(ci+1-ci)/(3hi), подставляя это выражение в (4) и исключая ai=yi-1, получим Подставив теперь выражения для bi, bi+1 и di в первую формулу (5), после несложных преобразований получаем для определения ci разностное уравнение второго порядка с краевыми условиями Условие cn+1=0 эквивалентно условию cn+3dnhn=0 и уравнению ci+1=ci+3dici при i=n.

Разностное уравнение (6) с условиями (7) решаются методом прогонки.

Можно ввести понятие сплайна порядка m как функции, которая является полиномом степени m на каждом из отрезков сетки и во всех внутренних узлах сетки удовлетворяет условиям непрерывности функции и производных до порядка m-1 включительно. Обычно для интерполяции используются случаи m=3 (рассмотренный выше кубический сплайн) и m=1 (линейный сплайн, соответствующий аппроксимации графика функции y(x) ломаной, проходящей через точки (xi, yi)).

Модуль 3. Численное интегрирование и решение систем алгебраических 3.4.1. Задача приближенного вычисления определенного интеграла следующие ситуации, требующие применения численного интегрирования: для заданного интеграла не существует первообразной («не берущийся» интеграл); первообразная сложна, и ее вычисление связано со значительными трудностями. В качестве приближенных значений интегралов в этих случаях естественно воспользоваться оценками по формулам, напоминающим интегральные суммы, т.е. линейные комбинации конечного числа значений подынтегральной функции на заданном сегменте:

членом квадратурной формулы.

При такой постановке возникают две задачи: 1) нужно определить, каким образом разбивать сегмент [a,b], и как выбирать узлы, чтобы получить возможно более точное значение интеграла; 2) необходимо решить проблему увеличения скорости сходимости интегральных сумм.

Часто рассматривают вычисление интегралов более общего вида где p(x) – весовая функция. Можно строить квадратурные формулы из разных соображений. Рассмотрим некоторые из них.

3.4.1.1. Квадратурные формулы с наилучшей точностью для данного класса функций Обозначим через R некоторый класс функций, интегрируемых по Риману. Пусть R n = sup Rn ( f ), где Rn(f) – остаточный член некоторой квадратурной формулы для функции f R. Ставится задача такого выбора узлов и коэффициентов квадратурной формулы, чтобы величина R n, т.е. точная верхняя грань по остаточным членам всех функций этого класса, была наименьшей. Такую формулу н6азывают формулой с наилучшей точностью для данного класса функций.

3.4.1.2. Квадратурные формулы с наилучшей степенью точности Пусть { k ( x)}k =0 – базисное множество в некотором пространстве функций, причем множество функций { k ( x)}k =0. Где n – фиксированное число, образует систему Чебышева порядка n (многочлен по этой системе имеет не более n корней). Обозначим через Фm(x) Зафиксируем число узлов квадратурной формулы n и будем подбирать ее коэффициенты и расположение узлов так, чтобы эта формула была точна для многочленов как можно более высокой степени m. Порядок многочлена m, для которого формула еще точна (при условии, что она уже не точна для многочлена порядка m+1) и называется степенью точности квадратурной формулы такого типа. Говорят, что это формула наилучшей степени точности m.

Чаще всего в качестве системы функций { k ( x)}k =0 выбираются степенные функции Пусть { k ( x)}k =0 – система функций Чебышева на сегменте [a,b], на котором также задана остаточный член квадратурной формулы интерполяционного типа. Коэффициенты c (n ) не зависят от f(x), а определяются только весовой функцией и узлами интерполяции.

Установим связь между квадратурной формулой интерполяционного типа и квадратурными формулами определенного порядка точности по отношению к определенному виду многочлена.

Теорема. Необходимое и достаточное условие того, чтобы квадратурная формула с n узлами была интерполяционной для системы функций { k ( x)}k =0, которая является системой Чебышева, заключается в следующем: эта формула должна иметь порядок точности не ниже n- интерполяционной формулой. Следовательно, эта формула точна, если в качестве функции f(x) интерполяционным многочленом, и остаточный член полинома Лагранжа равен нулю, а поэтому равен нулю и остаточный член квадратурной формулы.

Достаточность. Пусть квадратурная формула является точной по заданной системе функций для многочленов порядка не ниже n-1. В частности, эта формула будет точна для Итак, коэффициенты данной квадратурной формулы выражаются как коэффициенты интерполяционной формулы. Следовательно, данная квадратурная формула является интерполяционной.

Следствие. Интерполяционная квадратурная формула с n узлами по системе функций { k ( x)}n10 имеет порядок точности по этой системе функций не ниже, чем n-1.

3.4.1.4. Замечания к использованию квадратурных формул 1) При использовании квадратурных формул для вычисления интегралов основной объем работы содержится в вычислении значений функции в узлах интерполяционной формулы, т.к.

значения коэффициентов c (n ) табулированы. Следовательно, надо выбирать квадратурную формулу с минимальным числом узлов при обеспечении необходимой точности.

2) Если каждое из значений функции в квадратурной формуле вычисляется с погрешностью, то Отсюда вытекает, что необходимо при вычислениях использовать квадратурные формулы, которые имеют малые по абсолютной величине коэффициенты.

Такое название носят квадратурные формулы интерполяционного типа, построенные по равноотстоящим узлам. Различают формулы двух видов.

1) Формулы открытого типа. В этих формулах границы сегмента интегрирования [a,b] не входят в число узлов квадратурной формулы.

2) Формулы замкнутого типа. В этом случае точки a и b являются узлами квадратурной формулы.

Рассмотрим формулы второго типа.

Разобьем сегмент интегрирования [a,b] на n равных частей и в качестве узлов интерполирования возьмем точки деления и границы сегмента. Получим Интерполяционный полином Лагранжа для функции f(x) по этим узлам для системы степенных функций имеет вид Введем q=(x-x0)/h x=x0+qh; тогда поскольку x-xj-1=x0+hq-x0-h(j-1)=h(q-(j-1))=h(q-(j-1)); xj-xj-1=x0+hj-x0-h(j-1)=h. Здесь введено обозначение q[n+1]=q(q-1)…(q-j)…(q-n).



Pages:   || 2 | 3 |
 


Похожие работы:

«ОКРУЖАЮЩИЙ МИР К УЧЕБНИКУ А.А. Плешакова (М.: Просвещение) 2 -е издан ие, пер ер а б о тан н о е 1 класс МОСКВА • ВАКО УДК 373.167.1:502 ББК 74.262 К64 Контрольно измерительные материалы. Окружающий К64 мир: 1 класс / Сост. И.Ф. Яценко. – 2-е изд., перераб. – М.: ВАКО, 2011. – 96 с. – (Контрольно-измерительные материалы). ISBN 978-5-408-00380-8 В пособии представлены контрольно-измерительные материалы по курсу Окружающий мир для 1 класса в тестовой форме. Все задания соответствуют программе...»

«Министерство образования Российской Федерации ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) Кафедра автоматизированных систем управления (АСУ) Е.Н. Сафьянова ДИСКРЕТНАЯ МАТЕМАТИКА Часть 1 Учебное пособие 2000 Сафьянова Е.Н. Дискретная математика. Часть 1: Учебное пособие. Томск: Томский межвузовский центр дистанционного образования, 2000. 106 с. Учебное пособие рассмотрено и рекомендовано к изданию методическим семинаром кафедры автоматизированных систем...»

«ИЦ Физприбор Методические указания. Расчет эквивалентной площади и эквивалентных размеров отражателей в ультразвуковом контроле изделий. Разработчик: Специалист 3 уровня по акустическим методам НК, к.ф.-м.н. Бархатов В.А. Екатеринбург 2009 г. ОГЛАВЛЕНИЕ 1. Введение 2. Теоретические основы 3. Методики расчета эквивалентной площади и размеров отражателей, коррекция чувствительности ультразвукового дефектоскопа 3.1. Определение эквивалентной площади донной поверхности. Прозвучивание прямым...»

«1 2 Содержание 1 Цели и задачи освоения дисциплины. 2 Место дисциплины в структуре ООП ВПО. 3 Требования к результатам освоения содержания дисциплины 4 Содержание и структура дисциплины (модуля). 4.1 Содержание разделов дисциплины 4.2 Структура дисциплины 4.3 Лабораторные работы.. 4.4 Практические занятия (семинары)..10 4.5 Расчетно-графическая работа 4.6 Самостоятельное изучение разделов дисциплины.11 5 Образовательные технологии 5.1 Интерактивные образовательные технологии, используемые в...»

«ОАО Российские железные дороги РАБОЧЕЕ ВРЕМЯ И ЕГО УЧЕТ В ЕКАСУТР Методическое пособие для специалистов в области организации, нормирования и оплаты труда Автор проекта: Разуменко Г.В. Ведущий инженер НОТ Красноярская ж.д (в редакции ЦЗТ) Красноярск 2012г ОГЛАВЛЕНИЕ 1. Аннотация 2. Основные определения и сокращения 3. Предисловие 4. Общие положения Введение в Управление временными данными 4.1 5. Основные понятия рабочего времени. Особенности реализации отдельных его видов и режимов. Режим...»

«Е. М. Карчевский, И. Е. Филиппов, И.А. Филиппова Excel 2010 в примерах Учебное пособие Казанский университет 2012 СОДЕРЖАНИЕ ПЕРВЫЙ УРОК Первое знакомство Вычисления в таблицах данных Элементарная сортировка данных Графическое представление данных таблиц Задания для самостоятельной работы ВТОРОЙ УРОК Работа с диаграммами Использование рисунков в диаграммах Задания для самостоятельной работы ТРЕТИЙ УРОК Работа со списками Сортировка Использование фильтров Задания для самостоятельной работы....»

«МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ УЧЕБНОЙ ПРАКТИКИ ПО ИНЖЕНЕРНОЙ ГЕОЛОГИИ для студентов специальностей 270205 и 270201 Омск • 2011 30 Министерство образования и науки РФ ГОУ ВПО Сибирская государственная автомобильно-дорожная академия (СибАДИ) Кафедра инженерной геологии, оснований и фундаментов МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ УЧЕБНОЙ ПРАКТИКИ ПО ИНЖЕНЕРНОЙ ГЕОЛОГИИ для студентов специальностей 270205 и 270201 Составитель О.В.Тюменцева Омск СибАДИ УДК 624. ББК 26. Рецензент канд. техн....»

«ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ СЕВЕРО-КАВКАЗСКИЙ ГОРНО-МЕТАЛУРГИЧЕСКИЙ ИНСТИТУТ (ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ) КАФЕДРА АВТОМАТИЗИРОВАННОЙ ОБРАБОТКИ ИНФОРМАЦИИ Учебное пособие по курсу Технология программирования больших программных комплексов Составитель: М. Х.Томаев Владикавказ 2008 ОГЛАВЛЕНИЕ Введение 1. Основы методологии проектирования ИС 1.1. Жизненный цикл по ИС 1.2. Модели жизненного цикла ПО 1.3. Методологии и технологии проектирования ИС 1.3.1. Общие требования к...»

«1 Содержание 1. Цели учебной программы подготовки специалистов 4 2. Виды и задачи профессиональной деятельности выпускника 6 3. Перечень специализаций подготовки специалиста 21 4. Содержание дисциплин учебных циклов 22 5. Взаимосвязи видов и задач профессиональной деятельности выпускника с формируемыми компетенциями, проектируемыми результатами и изучаемыми дисциплинами 101 6. Межпредметные связи изучаемых дисциплин 335 7. Аннотация видов практической подготовки 346 8. Аннотация проведения...»

«Минобрнауки России Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Тульский государственный университет Институт международного образования Центр довузовской подготовки иностранных граждан Кафедра русского языка МЕТОДИЧЕСКИЕ УКАЗАНИЯ К САМОСТОЯТЕЛЬНОЙ РАБОТЕ СТУДЕНТОВ по дисциплине ДЕЛОВАЯ РИТОРИКА Направление подготовки: 010200, 010400, 010800, 020100, 020400, 080100, 120700, 161100, 090303, 151701, 160400, 160700, 170100, 170400, 034700,...»

«СТАНДАРТЫ МГУТУ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ Кафедра Организация производственной и коммерческой деятельности. Рассмотрено на заседании кафедры УТВЕРЖДАЮ Протокол № от 2007 г. Проректор по учебной Зам.зав.кафедрой ОП и КД,проф. работе, проф. Л.А Козловских. О.Е.Руденко 2007г 2007г. УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ Организация, нормирования и оплаты труда Для специальностей 080502 форм обучения: всех форм обучения...»

«ПРИЛОЖЕНИЕ 10 МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ОЦЕНКЕ ТРАНСФОРМАЦИИ/РАСТВОРИМОСТИ МЕТАЛЛОВ И ИХ СОЕДИНЕНИЙ В ВОДЕ - 543 Приложение 10 МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ОЦЕНКЕ ТРАНСФОРМАЦИИ/ РАСТВОРИМОСТИ МЕТАЛЛОВ И ИХ СОЕДИНЕНИЙ В ВОДЕ1 А10.1 Введение А10.1.1 Настоящие Методические указания по испытаниям предназначены для определения того, с какой скоростью и в какой степени металлы и умеренно растворимые соединения металлов способны образовывать в водной среде растворимые соединения, находящиеся в свободном...»

«2 ОГЛАВЛЕНИЕ Рабочая программа. 4 1. Методические указания и контрольные задания. 18 2. Исходные данные для выполнения контрольной 3. работы.. 28 3 РАБОЧАЯ ПРГРАММА дисциплины Основы геодезии и маркшейдерского дела I. Пояснительная записка. Рабочая учебная программа по дисциплине Основы геодезии и маркшейдерского дела составлена на основе ГОСО и типовой учебной программы. Рабочая учебная программа предназначена для обучающихся на базе основного и среднего общего образования по квалификациям...»

«ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ОСНОВАН В 1878 ГОДУ ДИССЕРТАЦИЯ МАГИСТРА ГЕОЛОГИИ Учебно-методическое пособие Томск - 2011 Министерство образования и науки Российской Федерации ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ДИССЕРТАЦИЯ МАГИСТРА ГЕОЛОГИИ Учебно-методическое пособие Томск - 2011 2 Диссертация магистра геологии : учебно-методич. пособие / сост. Г.М. Татьянин, Н.И. Савина, Я.А. Баженова ; Том. гос. ун-т. – Томск, 2011. – 50 с. Учебно-методическое пособие составлено на основе требований...»

«Томский межвузовский центр дистанционного образования Е.В. Дерябина ОРГАНИЗАЦИЯ, НОРМИРОВАНИЕ И ОПЛАТА ТРУДА НА ПРЕДПРИЯТИЯХ ОТРАСЛИ Учебное пособие 2006 Корректор: Осипова Е.А. Дерябина Е.В. Организация, нормирование и оплата труда на предприятиях отрасли: Учебное пособие. — Томск: Томский межвузовский центр дистанционного образования, 2006. — 224 с. Дерябина Е.В., 2006 Томский межвузовский центр дистанционного образования, 2006 3 СОДЕРЖАНИЕ ВВЕДЕНИЕ 1 ПРЕДМЕТ, ЗАДАЧИ И СОДЕРЖАНИЕ КУРСА 1.1...»

«УДК 004:001.8(075) ББК 32.973+20я73 И74 Электронный учебно-методический комплекс по дисциплине Информационнокоммуникационные технологии в естественнонаучных исследованиях подготовлен в рамках реализации Программы развития федерального государственного образовательного учреждения высшего профессионального образования Сибирский федеральный университет (СФУ) на 2007–2010 гг. Рецензенты: Красноярский краевой фонд науки; Экспертная комиссия СФУ по подготовке учебно-методических комплексов дисциплин...»

«2 и 3 ОГЛАВЛЕНИЕ АННОТАЦИЯ 1. ТРЕБОВАНИЯ К ДИСЦИПЛИНЕ 1.1. ВНЕШНИЕ И ВНУТРЕННИЕ ТРЕБОВАНИЯ 1.2. МЕСТО ДИСЦИПЛИНЫ В УЧЕБНОМ ПРОЦЕССЕ 2. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ. КОМПЕТЕНЦИИ, ФОРМИРУЕМЫЕ В РЕЗУЛЬТАТЕ ОСВОЕНИЯ. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЕ ДАННЫЕ ДИСЦИПЛИНЫ 4. СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ 4.1. СТРУКТУРА ДИСЦИПЛИНЫ 4.2. ТРУДОЁМКОСТЬ МОДУЛЕЙ И МОДУЛЬНЫХ ЕДИНИЦ ДИСЦИПЛИНЫ СОДЕРЖАНИЕ МОДУЛЕЙ ДИСЦИПЛИНЫ 4.3. 4.4. ЛАБОРАТОРНЫЕ/ПРАКТИЧЕСКИЕ/СЕМИНАРСКИЕ ЗАНЯТИЯ 4.5. САМОСТОЯТЕЛЬНОЕ ИЗУЧЕНИЕ РАЗДЕЛОВ...»

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ 11/1/1 Одобрено кафедрой Электрификация и электроснабжение ЭЛЕКТРОННАЯ ТЕХНИКА И ПРЕОБРАЗОВАТЕЛИ В ЭЛЕКТРОСНАБЖЕНИИ Задание на контрольную работу № 2 с методическими указаниями для студентов IV курса специальности 190401.65 ЭЛЕКТРОСНАБЖЕНИЕ ЖЕЛЕЗНЫХ ДОРОГ (ЭЛ) РОАТ Москва – 2011 Задание на контрольную работу содержит две типовые задачи и методические указания по их решению. Постановка задач заимствована из ранее выполнявшихся работ по...»

«МАТЕРИАЛЫ КОНФЕРЕНЦИИ 73 УПРАВЛЕНИЕ ПЕРСОНАЛОМ Приложение Интернет-ресурсы содержит ссылки на ведущие электронные ресурсы Панов Б.В., Шабалов В.А., Юрлов Ю.Н. наук и управления персоналом. Филиал СПбГИЭУ, Череповец, Дистрибутивы электронного учебника и деe-mail: chereng@rambler.ru мо-версия доступны на официальном сайте: www.chereng.ru. Особенности: Весь материал разбит на отдельные блоки – разделы, которые охватывают целостный круг во- БИЗНЕС-ПЛАН просов, объединенных по критерию направление...»

«2 3 Оглавление АННОТАЦИЯ 1. ТРЕБОВАНИЯ К ДИСЦИПЛИНЕ 2. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ. КОМПЕТЕНЦИИ, ФОРМИРУЕМЫЕ В РЕЗУЛЬТАТЕ ОСВОЕНИЯ. 3. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЕ ДАННЫЕ ДИСЦИПЛИНЫ 4. СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ 4.1. СТРУКТУРА ДИСЦИПЛИНЫ 4.2. ТРУДОЁМКОСТЬ МОДУЛЕЙ И МОДУЛЬНЫХ ЕДИНИЦ ДИСЦИПЛИНЫ СОДЕРЖАНИЕ МОДУЛЕЙ ДИСЦИПЛИНЫ 4.3. 4.4. ЛАБОРАТОРНЫЕ/ПРАКТИЧЕСКИЕ/СЕМИНАРСКИЕ ЗАНЯТИЯ. ОШИБКА! ЗАКЛАДКА НЕ ОПРЕДЕЛЕНА. 4.5. САМОСТОЯТЕЛЬНОЕ ИЗУЧЕНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ Перечень вопросов для...»







 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.