- •1. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ПОГРЕШНОСТЕЙ; ВЫЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ, МЕТОДЫ И АЛГОРИТМЫ
- •1.1. Источники и классификация погрешностей результата численного эксперимента
- •1.2. Погрешности чисел
- •1.3. Погрешности арифметических операций
- •1.4. Погрешности функций
- •1.5. Особенности машинной арифметики
- •1.6. Лабораторная работа № 1. Определение абсолютной и относительной погрешностей приближенных чисел. Оценка погрешностей результата
- •1.7. Корректность вычислительной задачи
- •1.8. Обусловленность вычислительной задачи
- •1.9. Вычислительные методы, их классификация
- •2. ПРИБЛИЖЕНИЕ ФУНКЦИЙ
- •2.1. Задача приближения функций
- •2.2. Интерполяция обобщенными многочленами
- •2.3. Полиномиальная интерполяция. Многочлен Лагранжа
- •2.4. Погрешность интерполяции
- •2.5. Конечные разности и их свойства
- •Доказательство
- •2.6. Разделенные разности и их свойства
- •2.9. Лабораторная работа № 2. Интерполирование и экстраполирование данных. Интерполяционный многочлен Лагранжа
- •2.10. Интерполяционный многочлен Ньютона с конечными разностями
- •2.11. Лабораторная работа № 3. Интерполирование и экстраполирование данных. Интерполяционный многочлен Ньютона
- •2.12. Интерполяционные формулы Гаусса, Стирлинга и Бесселя
- •3. МЕТОД НАИМЕНЬШИХ КВАДРАТОВ И СПЕЦИАЛЬНЫЕ ИНТЕРПОЛЯЦИОННЫЕ МНОГОЧЛЕНЫ
- •3.1. Постановка задачи и вывод формул метода наименьших квадратов
- •3.3. Глобальная полиномиальная интерполяция
- •3.4. Чувствительность интерполяционного многочлена к погрешностям входных данных
- •3.5. Многочлены Чебышева
- •3.6. Решение задачи минимизации оценки погрешности
- •3.8. Лабораторная работа №5. Экономизация степенных рядов
- •3.9. Локальная интерполяция
- •3.10. Сплайны, их свойства и построение
- •3.11. Погрешность приближения кубическими сплайнами
- •3.13. Тригонометрическая интерполяция. Дискретное преобразование Фурье и его реализация на ЭВМ
- •3.14. Матричная форма записи дискретного преобразования Фурье (ДПФ)
- •3.15. Алгоритм реализации ДПФ
- •3.16. Пример реализации алгоритма ДПФ при
- •3.17. Лабораторная работа № 7. Дискретное преобразование Фурье
- •4. ЧИСЛЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ И ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ
- •4.1. Простейшие формулы численного дифференцирования для первой производной
- •4.2. Формулы численного дифференцирования для второй производной
- •4.3. Формулы численного дифференцирования, основанные на интерполяции алгебраическими многочленами
- •4.4. Обусловленность формул численного дифференцирования
- •4.5. Простейшие квадратурные методы численного интегрирования
- •4.6. Оценка погрешностей простейших квадратурных формул
- •4.7. Квадратурные формулы интерполяционного типа
- •4.8. Квадратурные формулы Гаусса
- •4.9. Лабораторная работа № 8. Численное дифференцирование и численное интегрирование функций
- •5. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ И ПРОБЛЕМЫ СОБСТВЕННЫХ ЗНАЧЕНИЙ
- •5.1. Нормы векторов и матриц и их свойства
- •5.2. Обусловленность задачи решения системы линейных алгебраических уравнений
- •5.3. Метод Гаусса (схема единственного деления)
- •5.4. Метод прогонки
- •5.5. Метод простых итераций
- •5.6. Сходимость метода простых итераций
- •5.10. Постановка задачи нахождения собственных чисел
- •5.11. Подобные матрицы
- •5.12. Локализация собственных значений
- •5.13. Степенной метод
- •5.14. Вычисление собственных векторов методом обратных итераций
- •6. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ И СИСТЕМ
- •6.1. Решение нелинейных уравнений
- •6.2. Метод Ньютона для уравнений
- •6.3. Сходимость метода Ньютона и трудности его применения
- •6.4. Метод Ньютона решения систем нелинейных уравнений
- •6.6. Модификации метода Ньютона
- •6.7. Лабораторная работа № 11. Решение систем нелинейных уравнений методом Ньютона
- •7. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ КОШИ ДЛЯ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ И СИСТЕМ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ
- •7.1. Задача Коши для дифференциального уравнения первого порядка
- •7.2. Численные методы решения задачи Коши. Основные понятия и определения
- •7.3. Решение с помощью рядов Тейлора
- •7.5. Анализ ошибок, возникающих при использовании методов Рунге - Кутты
- •7.6. Методы прогноза и коррекции
- •7.7. Сравнение методов
- •7.8. Лабораторная работа № 12. Методы интегрирования обыкновенных дифференциальных уравнений
- •7.9. Решение задачи Коши для систем обыкновенных дифференциальных уравнений
- •7.11. Лабораторная работа № 13. Численное интегрирование систем дифференциальных уравнений первого порядка
- •8. ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ С ЧАСТНЫМИ ПРОИЗВОДНЫМИ (УРАВНЕНИЯ МАТЕМАТИЧЕСКОЙ ФИЗИКИ)
- •8.1. Классификация уравнений математической физики
- •8.2. Простейшие задачи, приводящие к дифференциальным уравнениям в частных производных
- •8.4. Уравнения параболического типа. Явные и неявные схемы
- •Доказательство
- •8.5. Уравнения гиперболического типа
- •8.6. Уравнения эллиптического типа
- •8.7. Свойства разностных схем для дифференциальных уравнений: способность аппроксимировать исходную дифференциальную задачу, устойчивость и сходимость
- •8.8. Некоторые обобщения
- •8.9. Лабораторная работа № 14. Решение задачи Дирихле для уравнения Лапласа методом сеток
- •8.10. Лабораторная работа № 15. Решение однородного уравнения колебаний струны методом сеток по неявной схеме.
С помощью панели форматирования первый график повернут на 30o , и на нем убраны невидимые линии, оси второго графика оцифрованы по x и y в пределах от 0 до 30.
1.7. Корректность вычислительной задачи
Анализ важнейших требований, предъявляемых к различным прикладным задачам, приводит к понятию корректности математической задачи.
Вычислительная задача называется корректной, если выполняются следующие три требования: а) решение этой задачи y Y существует при любых x X , б) это ре-
шение единственно, в) решение устойчиво по отношению к малым возмущениям входных данных. Если не выполнено хотя бы одно из условий, задача называется некорректной.
Существование решения - естественное требование. Отсутствие решения свидетельствует либо о непригодности принятой математической модели, либо о неправильной постановке самой математической модели.
Неединственность - неприятное свойство вычислительной задачи. Ее причиной, помимо уже перечисленных условий, может быть естественное свойство решаемой задачи. Неединственность может быть ликвидирована введением некоторых дополнительных ограничений на решение. Иногда за решение задачи принимается множество решений.
Решение y называется устойчивым по входным данным x , если y зависит от x непрерывным образом. Строго формальное определение устойчивости решения похоже на определения предела функции: если для любого ε > 0 найдется такое δ = δ(ε)> 0 , что для любого xi X , удовлетворяющего условию (xi )< δ , найдется соответствующее yi Y , такое, что (yi )< ε , решение будет устойчиво. Иными словами, для устойчивости вычислительной задачи ее решение теоретически можно найти со сколь угодно высокой точностью
ε, если обеспечена высокая точность δ исходных данных. Неустойчивость решения y |
оз- |
начает, что ε0 > 0, что какое бы малое δ > 0 ни было задано, найдутся такие данные |
xi , |
что (xi ) < δ, но (yi ) > ε0 . |
|
22 |
|
1.8. Обусловленность вычислительной задачи
Под обусловленностью вычислительной задачи понимают ее чувствительность к ма-
лым погрешностям входных данных. Задачу называют хорошо обусловленной, если ма-
лым погрешностям входных данных отвечают малые погрешности решения, и плохо обусловленной, если возможны сильные изменения решения. Для измерения количест-
венной стороны обусловленности используют число обусловленности. Грубо говоря, это ко-
эффициент возможного возрастания погрешностей в решении |
по отношению к вызвавшим |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
их погрешностям входных данных, то есть |
(yi ) = v |
|
|
|
(xi ), где v |
- абсолютное число обу- |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
словленности. |
Если |
|
|
|
|
δ(yi )= vδ |
δ(xi ), то |
vδ - |
относительное число обусловленности. Для |
|||||||||||||||||||||||||||||||||||||||||||||||||||||
плохо обусловленной задачи |
v >> 1. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
Пример. |
Вычисление |
значений |
функции |
|
|
|
одного |
|
переменного. |
При |
этом |
|||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
f / (x) |
|
|
|
|
|
|
|
|
|
(y )= |
|
|
f / (x) |
|
|
(x ) |
и |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
v = |
|
f / (x) |
|
и vδ |
= |
|
|
|
|
|
|
в силу формул |
|
|
|
|
|
|
|
x |
|
|
|
f / (x) |
|
|
δ (x ). Вычислим y = sin x . |
|||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
δ(y )= |
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
f |
(x) |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f (x) |
|
|
|
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
v |
|
|
|
|
|
cos x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
В этом случае |
= |
|
|
≤1, что говорит о хорошей абсолютной обусловленности этой за- |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
дачи при всех |
x . Однако если важен результат с определенным числом верных знаков, то |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
нужно |
использовать |
|
относи- |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
тельную |
|
обусловленность. |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Тогда |
vδ |
= |
|
x ctgx |
|
. |
|
График |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
функции |
y = |
|
x ctgx |
|
приве- |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ден слева. Так как |
|
vδ |
→ ∞ |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
при x → π k , то при |
|
x ≈ πk |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
задача обладает плохой отно- |
||||||||||||||||
0 |
|
π/2 |
|
|
|
|
|
|
|
|
π |
3π/2 |
2π |
|
5π/2 |
|
|
|
|
сительной обусловленностью, |
||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y = sin x . Если же значение |
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
хотя мала абсолютная по- |
||||||||||||||||||||||||||||||||
грешность значения |
|
|
|
|
|
|
|
|
очень велико, то vδ |
>> 1. |
Например, |
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
для ЭВМ РС при εm |
|
≈ 10−7 и при |
|
x |
|
≈107 |
одна только абсолютная ошибка |
|
(x )≈1. |
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
1.9. Вычислительные методы, их классификация
Методы, которые используются в вычислительной математике для преобразования задач к виду, удобному для реализации на ЭВМ, и позволяют конструировать вычислительные алгоритмы, называются вычислительными.
Они разделяются на следующие классы:
1)методы эквивалентных преобразований;
2)методы аппроксимации;
3)прямые (точные) методы;
4)итерационные методы;
5)методы статистических испытаний (Монте-Карло). Поясним классификацию подробнее.
Методы эквивалентных преобразований позволяют заменить исходную задачу дру-
гой, имеющей то же решение. Это целесообразно, если новая задача проще исходной или обладает лучшими свойствами, или для нее, например, существует уже готовый метод и программа, а для исходной задачи их надо создавать заново.
23
Пример. Задача отыскания корней уравнения y = f (x)= 0 может быть сведена к эквивалентной задаче поиска точки глобального минимума функции Φ(x)= (f (x))2 .
Методы аппроксимации приближают исходную задачу другой, решение которой в оговоренном смысле близко к решению исходной задачи. Погрешности, возникающие при такой замене, называются погрешностями аппроксимации. Как правило, аппроксимирующая задача содержит параметры, позволяющие регулировать величину погрешности аппроксимации.
Пример. Формула прямоугольников вычисления определенного интеграла:
b |
n |
|
|
1 |
|
|
|
b − a |
|
|
I = ∫ f (x)dx Iвыч |
= h∑ f a + i − |
|
h , где |
h = |
|
- параметр, регулирующий |
||||
2 |
n |
|||||||||
a |
i=1 |
|
|
|
|
|
|
точность.
Прямые методы позволяют получить решение исходной задачи после выполнения конечного числа элементарных операций.
Пример. x2 + bx + c = 0 , метод вычисления корней x1,2 = (− b ± b2 − 4ac)/ 2. Здесь элементарными считаются четыре арифметические операции и операция извлечения квадратного корня. Элементарной операцией метода может быть объявлена любая другая операция, необходимо, конечно, чтобы ее выполнение было существенно проще решения всей задачи.
Итерационные методы - специальные методы, приспособленные для построения последовательных приближений к точному решению задачи. Для получения каждого из последующих приближений выполняют однотипный набор действий с использованием ранее найденных приближений - итераций («iteratio»- повторение). Неограниченное продолжение этого процесса позволяет построить бесконечную последовательность приближений к решению - итерационную последовательность. Если она сходится к решению, то говорят, что итерационный метод сходится.
Множество начальных приближений, для которых метод сходится, называется областью сходимости метода. Практическая реализация итерационных методов всегда связана с необходимостью выбора критерия окончания итерационного процесса.
|
Пример. |
|
Вычислим |
a |
(a > 0). Пусть |
x(0) = 1 > 0. Воспользуемся формулой |
|||||
|
1 |
|
− |
|
a |
|
|
|
|
|
|
x(i ) = |
|
x(i 1) + |
|
|
|
, получим |
итерационную |
последовательность x(0), x(1),..., x(n ),... |
|||
2 |
x |
(i−1) |
|||||||||
|
|
|
|
|
|
|
= 1.41(6), x(3) = 1.4142156... . Известно, что метод сходится |
||||
a = 2 : x(0) |
= 1, |
x(1) |
= 1.5, x(2) |
при любом начальном приближении x(0) > 0.
Метод статистических испытаний основан на моделировании различных случайных величин и построении оценок. Этот метод применяют для решения не только тех задач, в которых в явном виде имеются случайные события, но также и для решения многих задач, не содержащих таких событий. В этом случае искусственно подбирают такое случайное явление, характеристики которого связаны с результатом решения исходной задачи. Для определения числовых значений этих характеристик и используется метод статистических испытаний.
Его главная идея основана на законе больших чисел, сам метод использует аппарат математической статистики.
Пример. Вычисление функций плотностей вероятностей различных законов, вычисление многомерных интегралов и тому подобные вопросы.
24