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

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

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

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

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

Y=0

L4(0)=0,1541658

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

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

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

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

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

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

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

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

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

Запишем исходную систему уравнений в векторно-матричном виде , где A- квадратная невырожденная матрица. Затем необходимо преобразовать систему к виду

x=Bx+c,

где В- квадратная матрица с элементами bij (I,j=1,2,3…m) c- вектор-столбец с элементами ci (i=1,2,3…m)

В развёрнутой форме записи система имеет вид:

x1=b11x1+b12x2+b13x3+…b1mxm+c1

x2=b21x1+b22x2+b23x3+…b2mxm+c1

x3=b31x1+b32x2+b33x3+…b1mxm+c3

xm=bm1x1+bm2x2+bm3x3+…bmmxm+cm

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

Самым простым способом приведения системы к такому виду является тот, что описан ниже:

И первого уравнения системы выразим x1:

x1=a11-1(b1-a12x2- a13x3-…- a1mxm)

Из второго уравнения системы выразим x2:

x2=a22-1(b2-a21x2- a23x3-…- a2mxm)

xm=amm-1(bm-am1x2- am3x3-…- am-1mxm-1)

В результате получим систему:

x1=0+ b12x2+ b13x3-…+ b1m-1xm-1+ b1mxm+c1

x2= b21x2+0 +b23x3+…+ b2m-1xm-1+ b2mxm+c2

xm= bm1x1+ bm2x20 +bm3x3+…+ bmm-1xm-1+ 0+cm

в которой, на главной диагонали матрицы B находятся нулевые элементы, стальные элементы выражаются по формулам:

bij=-aij/aii ci=bi/aii (i,j=1,2,3…m, i<>j)

Итерационный процесс продолжается до тех пор , пока значения х1(k) , х2(k) , х3(k) не станут близкими с заданной погрешностью к значениям х1(k-1) , х2(k-1) , х3(k-1) .

Для возможности выполнения данного преобразования необходимо, чтобы диагональные элементы матрицы А были ненулевыми.

Часто систему преобразуют к виду x=x-(Ax-b), где -специально выбираемый числовой параметр.

Описание метода:

Выберем начальное приближение x0=( x01 x02… x0m)

подставляя его в праву часть системы

x=Bx+c,

и вычисляя полученное выражение, находим первое приближение:

x1=Bx0+c

на втором шаге подставляем приближение x1 в правую часть той же системы, получим второе приближение:

x2=Bx1+c

Продолжая этот процесс далее, получим последовательность x1 x2 x3… xn приближений, вычисляемых по формуле :

Эта формула и выражает собой метод простой итерации.

Итерационный процесс продолжается до тех пор, пока значения х(k) не станут близкими с заданной погрешностью к значениям х(k-1).

Теорема. Метод простой итерации сходится тогда и только тогда, когда все собственные числа матрицы по модулю меньше единицы, т.е. либо .Эти выражения являются условиями сходимости метода итераций

3.2 Метод Зейделя

Метод Зейделя можно использовать как модификацию метода простых итераций. Основная идея модификации состоит в том, что при вычислении очередного (k+1)-го приближения к известному xi при i>1 используют используются уже найденные приближения к известным x1,… xi-1, а не k-е приближение как в методе простых итераций.

На (k+1)-й итерации компоненты приближения вычисляются по формулам:

Условие сходимости метода Зейделя заключается в том, что матрица A системы Ax=b, должна удовлетворять условию:

модуль диагонального элемента должен быть больше суммы модулей оставшихся элементов строки или столбца.

Если данное условие выполнено, необходимо проследить, чтобы система была приведена к виду, удовлетворяющему решению методом простой итерации и выполнялось необходимое условие сходимости метода итераций:

, либо

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

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

Выполним проверку на условие сходимости:

Условие выполнено, можно приступать к вычислению нулевого шага:

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

Проверим выполняется ли условие остановки итерационного процесса::

Условие остановки на первом шаге итерации не было выполнено, поэтому продолжаем итерацию, вычисляя x(2) :

Проверим выполняется ли условие остановки итерационного процесса::

Условие остановки на втором шаге итерации не было выполнено, поэтому продолжаем итерацию, вычисляя x(3) :

Проверим выполняется ли условие остановки итерационного процесса::

Условие остановки на третьем шаге итерации было выполнено лишь для x4, поэтому продолжаем итерацию, вычисляя x(4) :

Проверим выполняется ли условие остановки итерационного процесса:

Сходимость в сотых долях имеет место уже на 4-ом шаге, тогда можно принять

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

Решим ту же систему линейных уравнений методом Зейделя с той же точностью : .

Проверку на условие сходимости мы выполнили ранее, при решении методом простых итерации.

Проверим выполняется ли условие остановки итерационного процесса:

:

Условие остановки на первом шаге итерации не было выполнено, поэтому продолжаем итерацию, вычисляя x(2) :

Проверим выполняется ли условие остановки итерационного процесса:

:

Условие остановки на втором шаге итерации было выполнено лишь для x3, x4, поэтому продолжаем итерацию, вычисляя x(3) :

Проверим выполняется ли условие остановки итерационного процесса:

:

Условие сходимости выполнено на 3-ем шаге .

Корнями уравнения можно принять:

Как видно из вышеизложенных вычислений, скорость сходимости итерационного метода Зейделя выше, чем скорость сходимости метода простой итерации.

Ниже приведена сравнительная таблица1, позволяющая сравнить результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации:

Таблица1. Сводная таблица значений элементов приближений двух методов итерации

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

Рисунок 12. Решение системы уравнений методом простых итераций

Рисунок 13. Решение уравнения методом Зейделя

Раздел 4. Сравнительный анализ методов численного дифференцирования и интегрирования

4.1 Методы численного дифференцирования

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

Предположим, что в окрестности точки xi функция F(x)дифференцируема достаточное число раз. Исходя из определения производной:

используем для её вычисления две приближенные формулы:

(1)

(2)

Формулы (1) и (2) называют правыми и левыми разностными производными.

Для оценки погрешностей формул численного дифференцирования используется формула Тейлора:

откуда можно вычислить:

(3)

Выражение (3) имеет погрешность порядка (x-xi), следовательно, формулы правых и левых разностных производных имеют погрешность одного порядка с h , где

h=xi-xi-1

Такая точность достаточно невысока, поэтому применяется так называемая центрально-симметричная форма производной, погрешность которой одного порядка с h2

(4)

Хотя очевидно, что формула (4) используется для внутренних точек отрезка.

Для примера возьмём ряд точек:

Вычислим производную функции f(x)=sin(x) в одной из них двумя способами.

Очевидно, что h=

По центрально-симметричной формуле:

По формуле левой разностной производной:

Табличное значение =cos()=0.8660 ,т.е. значение производной, полученное по центрально-симметричной формуле ближе к истинному.

4.2 Методы численного интегрирования

В прикладных исследованиях часто возникает необходимость вычисления значения определённого интеграла

Как известно из курса математики, аналитически вычисление интеграла можно провести не во всех случаях. И даже в том случае, когда удаётся найти аналитический вид этого интеграла, процедура вычисления даёт приближённый результат, поэтому возникает задача приближенного значения этого интеграла.

Страницы: 1, 2, 3