ВЫЧИСЛЕНИЕ ЗНАЧЕНИЙ ПОЛИНОМОВ ПО СХЕМЕ ГОРНЕРА


АППРОКСИМАЦИЯ ФУНКЦИЙ. ПОНЯТИЕ АППРОКСИМАЦИИ

Пусть дана функция y=f(x), причем явная связь между y и x или неизвестна, или эта зависимость содержит трудно вычисляемые выражения, так что ее использование в практических расчетах затруднительно.

В таких случаях задают эту связь в виде некоторой таблицы {xi ,yi}, т.е. дискретному множеству значений аргумента {хi} ставят в соответствие множество значений функции {уi} (i=0, 1, ... , n). Отметим, что функциональная зависимость может сразу быть задана в виде таблицы, например, результаты эксперимента.

Встает проблема – как определить значения функции для промежуточных значений аргумента. Для этого надо данную функцию f(x) приближенно заменить (приблизить, аппроксимировать[1]) некоторой другой функцией j(х) так, чтобы отклонение j(х) от f(x) в заданной области было наименьшим, а вид и вычисление функции j(х) были более простыми.

Функция f(x) называется аппроксимируемой, а j(х) – аппроксимирующей. Часто в качестве аппроксимирующей функции выбирают многочлен:

j(х)= Pn(x)= а0 + а1 х+ а2х2 + ... + аn xn .

Если приближение строится на заданном дискретном множестве точек {хi} (таблица), тогда аппроксимация называется точечной (например, интерполирование). Приближение можно также строить и на непрерывном множестве точек (отрезок [a, b]), тогда аппроксимация называется непрерывной или интегральной.

В этой главе мы рассмотрим некоторые способы построения приближенных формул для заданной функции:

1) аппроксимация многочленами Тейлора (рядами);

2) интерполирование;

3) среднеквадратичная аппроксимация;

Все эти приближения реализуются алгебраическими многочленами (полиномами).

 

ВЫЧИСЛЕНИЕ ЗНАЧЕНИЙ ПОЛИНОМОВ ПО СХЕМЕ ГОРНЕРА

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

На первый взгляд, наиболее естественный способ – провести n–1 умножений, найдя степени x . Затем, выполнив еще n умножений и n сложений, получить Pn(x). Итого 3n–1 действий.

Другой способ, называемый схемой Горнера, состоит в перезаписи полинома в виде

Pn(x) = a0 + x( a1+ x(a2+ ... + x(an–2+ x(an–1+ xan )) ... ) .

Эта запись легко программируется. Поиск Pn(x) организуется следующим способом:

bn = an ; bn–1 = an–1 + x bn ; bn–2 = an–2 + x bn–1 ; ...

b1 = a1 + x b2 ; b0 = a0 + x b1 = Pn (x ).

Этот способ реализуется за n умножений и n сложений, итого 2n действий[2].

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

Схема счета вручную очень наглядна и имеет вид:

аn an–1 an–2... a0 x

+ x bn x bn–1 ... x b1

bn = an bn–1 bn–2 ... b0 = Pn (x).

Пример 1. Вычислить P3= 6x347x2 +12x +27 при х=8.

6 -47 12 27 8

+ 48 8 160

6 1 20 187 = P3(8).

 

Схему Горнера удобно применять для проведения замены х = у + x в полиномах Pn(x).

Известно, что всегда можно полином n-ой степени поделить на бином х–x , в общем случае с остатком, т.е.

Pn(x) = (bn xn–1 + bn–1xn–2 + ... +b1)(x – x) + b0,

где, очевидно, b0 = Pn(x) .

C другой стороны, если произвести в Pn(x) замену x = y + x , то, раскрыв скобки и сгруппировав подобные, получим:

Pn(y+x) = An yn + An–1yn–1 + ... + A1 y + A0 =

= (An yn–1 + An–1yn–2 + ... + A1)y + A0.



Дата добавления: 2020-10-25; просмотров: 484;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.008 сек.