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

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

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

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

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

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

j(х)= P_n(x)= а₀ + а₁ х+ а₂х² + ... + а_n xⁿ .

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

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

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

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

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

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

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

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

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

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

P_n(x) = a₀ + x( a₁+ x(a₂+ ... + x(a_n–2+ x(a_n–1+ xa_n )) ... ) .

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

b_n = a_n ; b_n–1 = a_n–1 + x b_n ; b_n–2 = a_n–2 + x b_n–1 ; ...

b₁ = a₁ + x b₂ ; b₀ = a₀ + x b₁ = P_n (x ).

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

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

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

а_n a_n–1 a_n–2... a₀ x

+ x b_n x b_n–1 ... x b₁

b_n = a_n b_n–1 b_n–2 ... b₀ = P_n (x).

Пример 1. Вычислить P₃= 6x³– 47x² +12x +27 при х=8.

6 -47 12 27 8

+ 48 8 160

6 1 20 187 = P₃(8).

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

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

P_n(x) = (b_n x^n–1 + b_n–1x^n–2 + ... +b₁)(x – x) + b₀,

где, очевидно, b₀ = P_n(x) .

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

P_n(y+x) = A_n yⁿ + A_n–1y^n–1 + ... + A₁ y + A₀ =

= (A_n y^n–1 + A_n–1y^n–2 + ... + A₁)y + A₀.