Новости Словари Конкурсы Бесплатные SMS Знакомства Подари звезду
В нашей
базе уже
59876
рефератов!
Логин

Пароль

Методы решения линейных уравнений

Методы решения линейных уравнений.
Методы решения линейных уравнений



Интерполяция по Ньютону Итак, дана табличная функция: i x y 0 x0 y0 1 x1 y1 2 x2 y2 ... ... ... n xn yn i = 0, 1, 2, ..., n Количество узловых точек N = n + 1. Необходимо найти значение этой функции в промежуточной точке, например, x = D, причем D([x0, xn]. Для решения задачи строим интерполяционный многочлен по формуле Ньютона, который имеет вид: Ln(x) = f(x0) + (x - x0)(f(x0; x1) + (x - x0)(x - x1)(f(x0; x1; x2) + (x - x0)(x - x1)(x - x2)( (f(x0; x1; x2; x3) + ... + (x - x0)(x - x1) ... (x - xn-1)(f(x0; x1; ...; xn) (1) где n - степень многочлена, f(x0), f(x0; x1), f(x0; x1; x2), ..., f(x0; x1; ...; xn) - разделенные разности различных порядков. Разделенные разности Значения f(x0), f(x1), ..., f(xn), т.е. значения табличной функции в узлах, называются разделенными разностями нулевого порядка (k = 0). Отношение называется разделенной разностью первого порядка (k = 1) на участке [x0; x1] и равно разности разделенных разностей нулевого порядка на концах участка [x0; x1], разделенной на длину этого участка. Отношение называется разделенной разностью второго порядка (k = 2) на участке [x0; x2] и равно разности разделенных разностей первого порядка, разделенной на длину участка [x0; x2]. Отношение называется разделенной разностью n-го порядка (k = n) на участке [x0; xn] и равно разности разделенных разностей (n - 1)-го порядка, разделенной на длину участка [x0; xn]. Для произвольного участка [xi; xi+1] разделенная разность первого порядка равна . Для произвольного участка [xi; xi+2] разделенная разность второго порядка равна . Таким образом, разделенная разность k-го порядка на участке [xi; xi+k] может быть определена через разделенные разности (k - 1)-го порядка по рекуррентной формуле: , (2) где k = (1, n) = (1, N - 1); i = (1, N - k); n - степень многочлена; N = n + 1 - количество узлов в табличной функции. Заметим, что численное дифференцирование основано на использовании разделенных разностей. Лемма: алгебраический многочлен (1), построенный по формуле Ньютона, является интерполяционным, т.е. значения многочлена в узловых точках равны значениям табличной функции: Ln(xi) = f(xi) = yi, i = 0, 1, 2, ..., n. Прежде всего заметим, что разделенные разности f(x0; x1), f(x0; x1; x2), ..., f(x0; ...; xn) являются вполне определенными числами, поэтому функция (1) действительно является алгебраическим многочленом n-й степени. Очевидно, что при x = x0 многочлен (1) равен Ln(x0) = f(x0) = y0. Далее, пусть x = x1. Тогда, подставляя x в (1), имеем: Пусть x = x2. Тогда (3) где (4) Подставляя (4) в (3), окончательно получим Ln(x2) = f(x2) = y2 и т.д. Заметим, что решение задачи интерполяции по Ньютону имеет некоторые преимущества по сравнению с решением задачи по Лагранжу. Интерполяционный многочлен Лагранжа зависит от каждого значения табличной функции yi. поэтому, при изменении n интерполяционный многочлен Лагранжа требуется строить заново. Интерполяционный многочлен Ньютона (1) выражается не через значения табличной функции yi, а через ее разделенные разности. Поэтому, при изменении степени многочлена n требуется только добавить или отбросить соответствующее число стандартных слагаемых в (1). Это удобно на практике и ускоряет процесс вычислений. Программирование формулы Ньютона Прежде всего, избавимся в формуле (1) от нулевых индексов. В результате получим: (5) где N = n + 1 - количество узловых точек в таблице; f(x1; x2)- разделенная разность первого порядка на участке [x1; x2]; f(x1; x2; x3) - разделенная разность второго порядка на участке [x1; x3]; f(x1; x2; ...; xN) - разделенная разность (xN-1)-го порядка на участке [x1; xN]. В программе разделенные разности f(x1), f(x1; x2), ..., f(x1; x2; ...; xN) для каждого k-го порядка будем помещать в массив Y. Тогда рекуррентная формула (2) будет иметь вид: , k = (1, N - 1), i = (1, N - k) (6) При этом в формуле (1) используются разделенные разности k-го порядка, подсчитанные только для участков [x1; x1+k], т.е. при i = 1. Разделенные разности, подсчитанные для i > 1 используются для дальнейших расчетов разделенных разностей более высоких порядков, (k + 1) и выше. Используя (6), свернем формулу (5). В результате получим: , где (yk)1 - разделенная разность k-го порядка, рассчитывается по формуле (6), в формуле (7) используется только для i = 1, Pk = (x - x1)(x - x2)...(x - xk) = . Для вычисления Pk удобно использовать рекуррентную формулу Pk = Pk-1(x - xk) внутри цикла по k. Блок-схема алгоритма Здесь: D - значение аргумента, для которого необходимо решить задачу интерполяции; N - количество узловых точек табличной функции; xi, yi - координаты узловых точек.
Умар.Ш. был тут !!!!!
 
давайте изгоним мат !!!
 
ДОБРОЙ НОЧИ ОТ Ъ
ЛОКИ ИНО
 
ДМК МЭ
 
где инфааа?