Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Введение к курсу “Алгоритмы и методы вычислений”
В настоящее время исследование явлений и процессов, протекающих в реальной жизни, а также решение практических задач управления и прогнозирования, основаны на построении математической модели изучаемых объектов и анализе с помощью вычислительной техники этих математических моделей.
Такой метод исследования называется вычислительным экспериментом.
Для физических процессов математическая модель обычно записывается в виде набора уравнений, в которые в качестве коэффициентов входят характеристики тел или веществ, участвующие в процессе.
Проведение расчетов по математической модели невозможны без применения вычислительной математики.
Для того чтобы понять место численных методов в процессе решения с использованием ЭВМ задач, возникающих в практической деятельности человека, представим основные этапы этого процесса.
Пусть требуется исследовать какой-либо физический объект, явление, процесс.
Вычислительный эксперимент включает в себя следующие этапы.
Формулируются основные законы, управляющие объектом исследования, и строится соответствующая математическая модель, представляющая запись этих законов в математической форме.
После того, как задача сформулирована в математической форме, необходимо найти её решение. На этом этапе требуется применение вычислительной техники, и, следовательно, применение численных методов.
Под численными методами понимаются методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям, т.е. к тем действиям, которые доступны для реализации на ЭВМ.
Чтобы реализовать численный метод, необходимо составить программу для ЭВМ. После отладки программы наступает этап проведения вычислений и анализ результатов.
Полученные результаты изучаются с точки зрения их соответствия исследуемому явлению, и при необходимости вносятся поправки в численный метод и уточняется математическая модель.
При изучении курса предполагается, что математическая формулировка задачи уже есть, нужно же научиться ее решать с использованием численных методов. Заметим, что если математическая модель выбрана недостаточно корректно, то какие бы методы не применялись для расчетов с ней, полученные выводы будут ненадежны, а то и вовсе неправильны.
При проведении расчётов по математическим моделям на ЭВМ приходится решать математические задачи разного уровня сложности. Для решения этих задач на ЭВМ используются численные методы.
Источники и классификация погрешностей.
Решение, полученное численным методом, обычно является приближенным, т.е. содержит некоторую погрешность, причём погрешность вносится на каждом этапе вычислительного эксперимента.
Источниками погрешности приближенного решения являются:
1) Несоответствие математической модели изучаемому реальному явлению; погрешность исходных данных.
2) погрешность метода решения. Она связана с тем, что всякий численный метод воспроизводит исходную математическую модель приближенно.
3) Погрешности округлений в арифметических операциях.
Погрешности, соответствующие этим причинам, называют:
Численные методы в большинстве случаев сами являются приближенными. Это происходит потому, что численным методом обычно решается некоторая другая, более простая задача, чем исходная задача. В ряде случаев численный метод строится на базе бесконечного процесса, который в пределе приводит к искомому решению. Однако реальный предельный переход обычно не удаётся осуществить, и процесс прерывается на некотором шаге, даёт приближенное решение.
Для решения математических задач в основном существует три группы методов:
Таким образом, численные методы являются основным аппаратом решения математических задач, и их значимость будет только увеличиваться по мере совершенствования ЭВМ.
Численные методы бывают двух типов: прямые и итерационные. В прямых методах решение задачи достигается за конечное число шагов метода, в итерационных методах выполняется необходимое количество итераций метода до получения приближенного решения с заданной точностью.
Понятие итерационного метода
В основном численные методы являются итерационными. Итерация - это повторение совокупности операций или процедур для улучшения имеющегося (текущего) приближенного решения задачи. Путь - решение задачи, тогда итерационный метод строит, так называемую, итерационную последовательность приближений решения, при этом должно стремиться к с увеличением .
Алгоритм итерационного метода имеет следующую в схему:
2. На -ой итерации метода имеется текущее приближение решение . Далее вычисляется следующее приближение . Здесь есть совокупность операций или процедур для улучшения приближенного решения задачи, которая составляет суть конкретного численного метода.
3. Проверяется критерий останова, т.е. проверяется: является ли полученное приближение решения достаточно близким к . Если нет, то происходит переход к следующей итерации, т.е. к пункту 2.
Заметим, что вид критерия останова (т.е. прекращения вычислений по итерационному методу) зависит от типа решаемой математической задачи и особенностей численного метода.
Характеристики численных методов
Для оценки численных методов (т.е. сравнения между собой методов для решения одной математической задачи) вводят следующие их основные характеристики:
Под трудоемкостью метода понимается количество и качество вычислений, необходимых для достижения достаточно близкого приближения решения задачи.
Под порядком метода понимается требования к знаниям о функциях, входящих в математическую формулировку задачи (например, использование в методе производных этих функций):
Численный метод называется сходящимся, если приближение стремится к решению с увеличением . Одним из важнейших этапов при введении нового численного метода является теоретическое доказательство его сходимости (т.е. формулирование условий, при которых метод гарантированно сходится).
В основном различают следующие скорости сходимости методов.
Под устойчивостью к погрешностям вычислений понимается то, что применение численного метода приводит к решению задачи на ЭВМ, несмотря на ошибки округлений и вычислений.
Наиболее сложным вопросом является учёт погрешностей округления в арифметическим операциям. Величина вычислительной погрешности определяется двумя факторами.
Алгоритм называется устойчивым, если в процессе его работы вычислительная погрешность возрастает незначительно, и неустойчивым – в противном случае. При использовании неустойчивого вычислительного алгоритма накопление погрешностей округления приводит в процессе счёта к переполнению арифметического устройства ЭВМ.
Под устойчивостью к погрешностям в исходных данных понимается то, что при небольших погрешностях в исходных данных применение численного метода позволяет получить приближенное решение задачи с не очень большой погрешностью.
Численный метод считается удачно выбранным, если его погрешность в несколько раз меньше неустранимой погрешности, а вычислительная погрешность в несколько раз меньше погрешности метода. Если неустранимая погрешность отсутствует, то погрешность метода должна быть несколько меньше заданной точности.
Погрешность решения
Для оценивания точности численного метода введем понятие абсолютной и относительной погрешности решения.
Если - точное решение задачи, а - приближенное решение, то абсолютной погрешностью приближения называется некоторая величина , про которую известно, что
.
Относительной погрешностью приближения называют некоторую величину , про которую известно, что
.
Обратим внимание на то, что приближенное решение задачи , полученное с помощью численного метода, обычно зависит от выбранных параметров этого метода. Без ограничения общности, будем считать, что параметр у метода один (условно обозначим его через ) и при этом он удовлетворяет условию . Тогда абсолютная погрешность также завиcит от , т.е. .
Если существуют некоторые и (не обязательно целое) такие, что выполняется неравенство , то говорят, что абсолютная погрешность имеет порядок . Этим хотят подчеркнуть качественную (в отличие от количественной) зависимость погрешности приближенного решения задачи от параметра метода . Например, это показывает, что уменьшение значения параметра на один порядок приводит к уменьшению величины абсолютной погрешности на порядков.