Программная реализация итерационных методов

1.5 Программная реализация итерационных методов

Рисунок 7. Решение уравнения методом хорд

Рисунок 8. Решение уравнения методом касательных

Раздел 2. Интерполирование

Одним из основных типов точечной аппроксимации является интерполирование. Оно состоит в следующем: для данной функции  строим интерполирующую функцию φ(х), принимающую в заданных точках , те же значения , что и функция , т.е.

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

Рисунок 9. Интерполяция.

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

2.1 Многочлен Лагранжа

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

Будем искать интерполяционный многочлен в виде линейной комбинации многочленов степени n:

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

.

По аналогии получим

при i=1

,

при i=2

,

,

Подставляя полученные выражения в

,

находим

.

Эта формула определяет интерполяционный многочлен Лагранжа.

Обратное интерполирование заключается в установлении зависимости . Задача обратного интерполирования заключается в том, чтобы по заданному значению функции y определить соответствующее значение аргумента x.

Функция выглядит следующим образом:

Ln(y)=

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

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

Рисунок 10. График функции

В пункте 1.2 для этой функции был выбран отрезок [3,4] и проверен на единственность корня.

Примем

х0=-0.1

х1=0.0125

х2=0.125

х3=0.237

х4=0.35.

Тогда многочлен Лагранжа будет иметь вид:

Вычислим значения функции (многочлена Лагранжа) в узлах интерполяции и исходной функции в тех же точках.

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

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

Для сравнения выберем точки: середина крайней части отрезка х=0.29375 и середина части, содержащей точку (a+b)/2 - х=0.18125.

Результаты для точки находящейся в середине отрезка начинают различаться на 13 знаке после запятой; для крайней точки - на 14-ом знаке. Следовательно, точность данного метода достаточно велика.

Рисунок 11. График исходной функции и интерполяционного многочлена.

Используя эти же узловые точки проведем обратную интерполяцию и определим значение х при у=0.

Y=0

L4(0)=0,1541658

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

Решение найденное методом хорд: х=

Решение найденное методом касательных: х=

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

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

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

Применение итерационных методов для качественного решения СЛАУ требует серьёзного использования её структуры, специальных знаний и определённого опыта. Именно поэтому разработано большое число итерационных средств, каждый из которых ориентирован на решения сравнительно узкого числа задач, и существует довольно мало программ, реализующих эти методы. В курсе математического обеспечения САПР мы рассмаривали следующие итерационные методы решения СЛАУ: метод простой итерации, метод Зейделя.

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

Численные методы линейной алгебры

Скачать

18618

0

16

... уравнений (2) сводится к последовательному решению двух следующих систем уравнений с треугольными матрицами коэффициентов L Y = B; (6) U X = Y (7) линейный алгебраический уравнение численный где Y =  - вектор вспомогательных переменных. Такой подход позволяет многократно решать системы линейных ...

Сравнительный анализ методов оптимизации

Скачать

42464

5

31

... 4 - график унимодальной, но не выпуклой функции Таким образом, кроме перечисленных свойств, выпуклые функции обладают также и всеми свойствами унимодальных функций. 2. Прямые методы безусловной оптимизации Для решения задачи минимизации функции f (х) на отрезке [а; b] на практике, как правило, применяют приближенные методы. Они позволяют найти решение этой задачи с необходимой точностью ...

Численное интегрирование функций

Скачать

7913

0

3

... – остаточный член, характеризующий погрешность формулы. Заметим, что формулы вида (2) называют квадратурными формулами. Геометрический смысл численного интегрирования состоит в вычислении площади криволинейной трапеции, ограниченной графиком функции f(х), осью абсцисс и двумя прямыми х = а и х = b. Приближенное вычисление площади приводит к отбрасыванию в квадратурных формулах остаточного члена ...

Автоматизированный анализ проектирования на микроуровне

Скачать

47503

2

14

... задачи, а именно: 1. Создана расчетная схема анализа на основании сравнительного анализа численных методов, а также программных и технических средств их осуществления; 2. Создан выбор метода автоматизированного анализа объекта проектирования; 3. Спланирован и проведен эксперимент, анализируя результаты которого, приходим к выводу, что данная модель может использоваться с параметрами: r = 5 R = ...