Погрешности численных методов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОСУДАРСТВЕННОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧЕРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ЮЖНО-РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ

ТЕХНИЧЕСКИЙ УНИВЕСИТЕТ

(НОВОЧЕРКАССКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ)»

ВЫПОЛНИЛ:

СТУДЕНТ ФМФ II-1

КАПЛУНОВ НИКОЛАЙ

ПРЕПОДАВАТЕЛЬ:

КНЯЗЕВ СЕРГЕЙ ЮРЬЕВИЧ

НОВОЧЕРКАССК 2008

Содержание

Тема №1.

Модели и моделирование.

Погрешности численных методов.

Свойства численного решения.

Тема №2

Аппроксимация функций.

Метод 1. Интерполяционная формула Лагранжа.

Метод 2. Сплайны.

Метод 3. Сплайны третьей степени.

Метод 4. Метод наименьших квадратов.

Тема № 3

Решение нелинейных уравнений.

Метод 10. Метод половинного деления.

Метод 11. Метод простых итераций.

Метод 12. Метод хорд.

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

Тема № 4.

Решение систем линейных уравнений.

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

Метод 15. Метод прогонки.

Метод 16. Метод уточнения решения.

Метод 17. Метод Гаусса-Зейделя.

Тема № 5.

Решение систем не линейных уравнений.

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

Метод 19. Метод Ньютона для системы уравнений.

Метод 20. Метод возмущения параметров.

Тема № 6.

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

Метод 21. Метод прямоугольников

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

Метод 23. Метод Симпсона

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

Метод 26. Метод Монте-Карло.

Метод 27. Метод Монте-Карло для вычисления кратных интегралов.

Тема № 7.

Решение обыкновенных дифференциальных уравнений (ОДУ).

Метод 28. Метод Эйлера.

Метод 29. Модифицированный метод Эйлера.

Метод 30. Метод Рунге-Кутта.

Метод 31. Метод Рунге-Кутта для решения систем ОДУ.

Метод 32. Метод Рунге-Кутта для ОДУ высших порядков.

Метод 33. Метод стрельбы.

Метод 34. Метод конечных разностей (МКР) (метод сеток).

Тема № 8.

Решение дифференциальных уравнений с частными производными.

Уравнение теплопроводности.

Метод 35. Явная разностная схема для уравнения теплопроводности.

Метод 36. Не явная разностная схема для уравнения теплопроводности.

Тема №9.

Задачи оптимизации.

Метод 37. Метод половинного деления.

Метод 38. Метод золотого сечения.

Метод 39. Метод покоординатного подъёма (спуска).

Метод 40. Метод градиентного подъёма (спуска).

Метод 41. Метод наискорейшего подъёма.

Тема № 10.

Задания для самостоятельной проработки.

Транспортная задача.

Задача о ресурсах.

Волновое уравнение.

Уравнение Лапласа.

Тема1:

Модели и моделирование

Используется 3 моделирования:

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

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

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

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

Например: исследование течения жидкости по трубам различного диаметра, очевидно, что характер течения зависит от скорости, диаметра, плотности все они являются размерными, но из них можно сконструировать безразмерную величину число Рейнольдца:

Физически подобными будут течения с одинаковым числом Рейнольдца. Некоторые явления можно исследовать путем изучения какого-либо явления иной физической природы, но описываемого теме же математическими соотношениями, что и моделируемое явление.

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

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

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

Значение этапа:

Правильно выбранная математическая модель решает поставленную задачу наполовину. Математическая модель не определяется однозначно исследовательным объектом. Для ее разработки необходимо сформулировать упрощающие предположения лежащие в основе модели. Установить такие факторы необходимо (установить степень точности).

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

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

Пример построения математической модели:

Пусть поставлена следующая задача:

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

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

1. Камень можно рассмотреть как математическую точку (частицу);

2. Земля является инерциальной системой отсчета;

3. Действием воздуха можно пренебречь;

4. Кривизной земли можно пренебречь;

5. Ускорение свободного падения есть величина постоянная.

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

Перейдем к построению математической модели. Введем систему координат. Ее начало совместим с катапультой, ось х направим горизонтально в сторону движения камня, а ось у вверх. Момент броска примем за начальный момент времени. При сделанных предположениях движение камня определяется II Законом Ньютона, который в данном случае примет вид:

у F = m a

V₀ mg = ma математическая модель

V (0) = V₀ решаемой задачи

α r(0) = 0

x

V_x (0) = V₀cos α V_x(t) = V₀cos α =dx/dt x (t) = V₀cos α t

V_y (0) = V₀sin α V_y(t) = V₀sin α = dy/dt y (t) = V₀sin α -gt²/2

x (0) = 0 x (0) = 0

y (0) = 0 y (0) = 0

Подставив найденное время в формулу, получим решение искомой задачи

Предположим результаты 3-го этапа моделирования неудовлетворительными, и мы приходим к выводу о необходимости уточнения модели, при этом может оказаться, что уточнение модели приведет к возникновению ряда проблем, в результате чего реального улучшения модели может и не произойти. Предположим, что для уточнения модели необходимо учесть силу сопротивления воздуха, для этого мы выдвигаем предположение о том, что сила сопротивления пропорциональна скорости и направлена противоположно движению, т.е. сила сопротивления F_c = -kV, в результате II Закона Ньютона приводим m*dV/dt = m*g-k*V – это уравнение значительно сложнее, чем в предыдущей модели. Решаемую задачу и в этом случае можно получить аналитически, на максимальное расстояние аналитически не возможно найти.

Погрешности численных методов

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

1. Ошибки математической модели;

2. Ошибки в исходных данных;

3. Ошибки численного метода;

4. Ошибки округления.

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

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

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

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

Например: в замене типа real на тип double или extended. Однако такой путь не самый лучший. Кроме того, использование чисел большой разрядности приводит к рациональному использованию результатов ресурсов ЭВМ.

Рассмотрим возникновение ошибок округленных на нескольких примерах. Предположим ЭВМ оперирует с четырьмя разрядами цифр, т.е. результат представляет четырьмя значащими цифрами, это значит, что относительная погрешность составляет 0, 5*10^-3. Ошибки округления возникают при всех арифметических операциях.

Например: при суммировании относительная погрешность значительно возрастает, при вычитании двух близких по величине чисел.

Для ошибок округления не выполняются обычные правила арифметики.

Например: ошибка суммирования нескольких чисел зависит от порядка суммирования. Меньшая ошибка возникает тогда, когда суммирование начинается с наименьшего числа.

Для уменьшения ошибок округления необходимо придерживаться к следующим правилам:

1. По возможности избегать разности двух близких по величине чисел;

2. Сложение и вычитание в длинной последовательности начинать с наименьшего числа;

3. Использовать выражение а*(b-с), а/(b-с) вместо a*b-a*c, a/b-a/c;

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

Еще один тип связан с ограничением представления чисел на ЭВМ, все числа в компьютере по абсолютной величине находятся в интервале (m₀, M), где числа m₀ – машинный нуль, М – машинная бесконечность.