Читайте также:
|
|
Введение
Постановка задачи
Схема Горнера вычисления значений полиномов.
1. Составить программу для вычисления значения полинома Р(х) для каждого заданного х;
2. Определить коэффициенты полинома Q(x), являющегося частным при делении исходного на двучлен (x-z);
3. Найти границы x1, x2 действительных корней полинома Р(х);
4. Построить график Р(х) при хϵ[х0,х3], х0<х1 х3>х2.
5. Оценить погрешности вычисления полинома.
Метод решения
§ 1. Вычисление значений полинома. Схема Горнера
Пусть дан полином п-й степени
P(x)=a0xn+a1xn-1+…+an-1x+an (1)
с действительными коэффициентами ak(k = 0, 1,…,п). Положим, что требуется найти значение этого полинома при x = ξ:
Р(ξ) = а0 ξn + a1ξ n-1 +... + аn-1 ξ + аn. (2)
Вычисление числа P(ξ) удобнее всего производить следующим образом. Представим формулу (2) в виде
P(ξ) = (... (((а0 ξ + а1) ξ + а2) ξ + а3) ξ +... + аn-1) ξ + ап).
Отсюда, последовательно вычисляя числа
b0 = a0,
b1 = а1 + b1 ξ,
b2=a2 + b2 ξ,
........... (3)
bn=an+bn-1 ξ
находим bn=P(ξ).
Покажем, что числа b0 = a0, b1,..., bn-1 являются коэффициентами полинома Q(x), полученного в качестве частного при делении данного полинома Р(x) на двучлен х — ξ. B самом деле, пусть
Q (х) = β0xn-1+β1xn-2+…+βn-1 (4)
P(x)=Q(x) (x- ξ) + βn, (5)
причем на основании теоремы Безу остаток от деления βn=Р(ξ). Из формул (4) и (5) получим:
Р(x) = (β0xn-1 + β1xn-2 +... + βn-1) (x - ξ) + βn,
или, раскрыв скобки и сделав приведение подобных членов, будем иметь:
Р(х) = β0xn + (β1 - β0 ξ)xn-1 + (β2 – β1ξ)xn-2 + … + (βn-1 – βn-2ξ)x + (βn – βn-1 ξ).
Сравнивая коэффициенты при одинаковых степенях переменной х в левой и правой частях последнего равенства, получим:
β0 = a0,
β1 – β0ξ = a1,
β2 – β1ξ = a2,
.........
βn – βn-1ξ = an.
Отсюда
β0 = a0 = b0,
β1 = a1 + β0ξ = b1,
................
βn = an + βn-1ξ = bn,
что и требовалось доказать.
Таким образом, формулы (3) позволяют, не производя деления, определять коэффициенты частного Q(at), а также остаток Практически вычисления осуществляются по следующей схеме, называемой схемой Горнера:
a0 a1 a2 … an ξ
b0 ξ b1 ξ … bn-1 ξ
b0 b1 b2 … bn = P(ξ)
Пример 1. Вычислить значение полинома
Р(х) = 3х3 + 2х2-5х +7 при x = 3.
Решение. Составляем схему Горнера:
3 2 -5 7 3
9 33 84_________
3 11 28 91 = P(3)
Замечание. Пользуясь схемой Горнера, можно получить границы действительных корней данного полинома Р(х).
Положим, что при x = β (β>0) все коэффициенты bi в схеме Горнера неотрицательны, причем первый коэффициент положителен, т. е.
b0=а0>0 и bi 0 (i = 1, 2,..., п) (6)
Тогда можно утверждать, что все действительные корни xk (k=1, 2,...m; т п) полинома Р(х) расположены не правее β, т. е. xk β (k = 1, 2,...,m) (рис. 2).
В самом деле, так как
Р (х) = (b0xn-1 + … + bn-1) (x- β) + bп,
то при любом х>β в силу условия (6) будем иметь Р(х) >0, т. е. любое число, большее р, заведомо не является корнем полинома Р(х). Таким образом, имеем верхнюю оценку для действительных корней хк полинома.
Для получения нижней оценки корней xk составляем полином
(-1)пР(-х) = а0хп— а1xn-1+...+(- 1)паn.
Для этого нового полинома находим такое число x = α(α>0), чтобы все коэффициенты в соответствующей схеме Горнера были
x1 xm неотрицательны, за исключением
первого, который, очевидно, будет
-α 0 β x Р(x) положительным.Тогда со-
Рис. 2. гласно предыдущим рассуждениям
ных корней полинома (—1)nР(—x), очевидно, разных — xk(k=1, 2,...,m), имеем неравенство — xk α.
Следовательно, xk -α (k=1, 2,..., m). Таким образом, мы получили нижнюю границу -α действительных корней полинома Р(х).Отсюда следует, что все действительные корни полинома Р(х) расположены на отрезке [—α, β].
Пример 2. Найти границы действительных корней полинома
Р (х) = x 4 – 2 x 3 + З x 2 + 4х — 1.
Решение. Подсчитаем значение полинома Р(х), например, при x = 2. Пользуясь схемой Горнера, получим:
1 -2 3 4 -1 2
2 0 6 20
1 0 3 10 19
Так как все коэффициенты bi 0, то действительные корни хк полинома Р(х) (если они существуют) удовлетворяют неравенству xk<2. Верхняя граница действительных корней найдена. Перейдем к оценке нижней границы. Составим новый полином:
Q (x) = (-1)4Р(-х) = х4 + 2х3 + Зх2 - 4х - 1.
Подсчитывая значение полинома Q (x), например, при х=1, имеем:
1 2 3 -4 -1 1
1 3 6 2
1 3 6 2 1
Все коэффициенты bi>0, значит, -xk<1, т.е. xk>-1.
Итак, все действительные корни данного полинома нахо-дятся внутри отрезка [-1, 2].
Начало |
Ввод x,n |
S=0 |
i=1;n+1 |
Ввод k(i) |
Вывод q |
i=1;n |
S=S*x+k(i) |
Вывод S |
i=1;n+1 |
z=S*x+k(i) |
Вывод P(x) |
i=1;n+1 |
abs(k[i])>abs(k[i+]) |
q=abs(k[i]) |
к=abs(k[i])/abs(k[1])+1 e=-w |
Вывод e, w |
Конец |
Дата добавления: 2015-09-11; просмотров: 17 | Поможем написать вашу работу | Нарушение авторских прав |
<== предыдущая лекция | | | следующая лекция ==> |
ТЕМПЕРАТУРНЫЙ ЛИСТ | | | Текст программы |