Разработка и реализация численных алгоритмов. Полиномиальная интерполяция
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
погрешностей округления приводит в процессе счета к переполнению арифметического устройства ЭВМ.
Требования к вычислительным методам.
Одной и той же математической задаче можно поставить в соответствие множество различных дискретных моделей. Однако далеко не все из них пригодны для практической реализации. Вычислительные алгоритмы, предназначенные для быстродействующих ЭВМ, должны удовлетворять многообразным и зачастую противоречивым требованиям.
Можно выделить две группы требований к численным методам. Первая группа связана с адекватностью дискретной модели исходной математической задаче, и вторая группа - с реализуемостью численного метода на ЭВМ. К первой группе относятся такие требования, как сходимость численного метода, выполнение дискретных аналогов законов сохранения, качественно правильное поведение решения дискретной задачи. Вторая группа требований, предъявляемых к численным методам, связана с возможностью реализации данной дискретной модели на данной ЭВМ, т. е. с возможностью получить на ЭВМ решение соответствующей системы алгебраических уравнений за приемлемое время. Основным препятствием для реализации корректно поставленного алгоритма является ограниченный объем оперативной памяти ЭВМ и ограниченные ресурсы времени счета.
Реальные вычислительные алгоритмы должны учитывать эти обстоятельства, т. е. они должны быть экономичными как по числу арифметических действий, так и по требуемому объему памяти.
Рассмотрим численный метод решения систем линейных алгебраических уравнений
(1)
где А - матрица , - искомый вектор, - заданный вектор. Предполагается, что определитель матрицы А отличен от нуля, так что решение x существует и единственно. Для большинства вычислительных задач характерным является большой порядок матрицы А.
Методы численного решения системы (1) делятся на две группы: прямые методы и итерационные методы. В прямых (или точных) методах решение х системы (1) находится за конечное число арифметических действий. Примером прямого метода является метод Гаусса. Отметим, что вследствие погрешностей округления при решении задач на ЭВМ прямые методы на самом деле не приводят к точному решению системы (1) и называть их точными можно лишь отвлекаясь от погрешностей округления. Сопоставление различных прямых методов проводится обычно по числу арифметических действий (а еще чаще-по асимптотике при больших m числа арифметических действий), необходимых для получения решения. При прочих равных условиях предпочтение отдается методу с меньшим числом действий.
Итерационные методы (их называют также методами последовательных приближений) состоят в том, что решение х системы (1) находится как предел при последовательных приближений , где n - номер итерации. Как правило, за конечное число итераций этот предел не достигается. Обычно задается некоторое малое число (точность) и вычисления проводятся до тех пор, пока не будет выполнена оценка
(2)
Число итераций , которое необходимо провести для получения заданной точности (т. е. для выполнения оценки (2)), для многих методов можно найти из теоретических рассмотрений. Качество различных итерационных процессов можно сравнивать по необходимому числу итераций .
К решению систем линейных алгебраических уравнений сводится подавляющее большинство задач вычислительной математики. В настоящее время предложено колоссальное количество алгоритмов решения задач линейной алгебры, большинство из которых рассчитано на матрицы А специального вида (трехдиагональные, симметричные, ленточные, большие разреженные матрицы).
Прямые методы не предполагают, что матрица А имеет какой - либо специальный вид. На практике они применяются для матриц умеренного порядка (порядка ста). Итерационные методы можно применять и для матриц высокого порядка, однако их сходимость не очень быстрая.
.2 Интерполирование и приближение функции
Основная задача классической теории интерполяции заключается в следующем. Пусть известны значения некоторой функции y = f(x) в точках х0, х1, …, хn требуется заменить f(x) другой функцией F(x), которая бы просто вычислялась и была близка к f(x) в некотором смысле. К такой задаче можно прийти, если:
) функция f(x) задана таблично;
) вычисление значений f(x) трудоемко и требуется найти значения f(x) при x=xk. Чтобы эта задача была корректной, на функцию f(x) необходимо наложить дополнительные условия: например, потребовать непрерывность ее производных.
Способ приближения функции f(x) некоторой функцией F(x), основанный на требовании: F(xk)=f(xk) называется интерполированием или интерполяцией.
Чаще всего интерполирующую функцию F(x) находят в виде алгебраического многочлена. Такой способ приближения имеет в своей основе гипотезу, что на небольших отрезках изменения х функция f(x) может быть достаточно хорошо приближена с помощью параболы некоторого порядка, аналитическим выражением которой и будет алгебраический многочлен.
К интерполированию приходится иногда прибегать и в том случае, когда для функции f(x) известно и аналитическое представление, с помощью которого можно вычислять ее значения для любого значения х из отрезка [a, b], в котором она определена, но вычисление каждого значения сопряжено с большим объемом вычислений. Если в процессе решения задачи необходимо нах