Инструменты пользователя

Инструменты сайта


others:sxema_gornera

Различия

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

Ссылка на это сравнение

others:sxema_gornera [2014/11/27 09:07] (текущий)
Строка 1: Строка 1:
 +====== Схема Горнера ======
 +Разделить с остатком многочлен //f(x)// на ненулевой многочлен //g(x)// - это значит представить //f(x)// в виде //f(x) = g(x)s(x) + r(x)//, где //s(x)// и //r(x)// - многочлены и либо //r(x)=0//, либо ст. //r(x) < ст. g(x)//.\\
 +//S(x)// назовем неполным частным,​ а //r(x)// - остатком при делении //f(x)// на //g(x)//.\\
 +Неполное частное при делении можно найти с помощью простого правила,​ называемого схемой Горнера,​ которое,​ кстати,​ позволяет найти и остаток.\\
  
 +Пусть //f(x) = a<​sub>​n</​sub>​x<​sup>​n</​sup>​ + a<​sub>​n-1</​sub>​x<​sup>​n-1</​sup>​ + ... + a<​sub>​1</​sub>​x + a<​sub>​0</​sub>//,​ //​a<​sub>​n</​sub>​≠0//​ -  многочлен //n//-й степени. При делении его на //(x - c)// мы получим неполное частное //s(x)// и остаток //r//, т.е. //f(x) = (x - c)s(x) + r//.\\
 +Так как ст. //f(x) = n//, а ст. //(x - c) = 1//, то
 +ст. //s(x) = n - 1//, т.е. //s(x) = b<​sub>​n-1</​sub>​x<​sup>​n-1</​sup>​ + b<​sub>​n-2</​sub>​x<​sup>​n-2</​sup>​ + … + b<​sub>​1</​sub>​x +  b<​sub>​0</​sub>,​ b<​sub>​n-1</​sub>​ ≠ 0//.\\
 +Таким обрзом,​ имеем равенство:​\\
 +
 +//​a<​sub>​n</​sub>​x<​sup>​n</​sup>​ + a<​sub>​n-1</​sub>​x<​sup>​n-1</​sup>​ + … + a<​sub>​1</​sub>​x + a<​sub>​0</​sub>​ = (x - c)(b<​sub>​n-1</​sub>​x<​sup>​n-1</​sup>​ + b<​sub>​n-2</​sub>​x<​sup>​n-2</​sup>​ + … + b<​sub>​1</​sub>​x + b<​sub>​0</​sub>​) + r//.\\
 +
 +Многочлены,​ стоящие в левой и правой частях этого соотношения,​ равны, а значит,​ равны их соответствующие коэффициенты. Приравняем их, раскрыв предварительно скобки и приведя подобные члены в правой части данного равенства. Получим:​\\
 +
 +//a = b<​sub>​n-1</​sub>,​ a<​sub>​n-1</​sub>​ = b<​sub>​n-2</​sub>​ - cb<​sub>​n-1</​sub>,​ a<​sub>​n-2</​sub>​ = b<​sub>​n-3</​sub>​ - cb<​sub>​n-2</​sub>,​\\
 +a<​sub>​2</​sub>​ = b<​sub>​1</​sub>​ - cb<​sub>​2</​sub>,​ a<​sub>​1</​sub>​ = b<​sub>​0</​sub>​ - cb<​sub>​1</​sub>,​ a<​sub>​0</​sub>​ = r - cb<​sub>​0</​sub>//​.\\
 +
 +Напомним,​ что требуется найти неполное частное,​ т.е. его коэффициенты,​ и остаток.\\
 +Выразим их из полученных равенств:​\\
 +//​b<​sub>​n-1</​sub>​ = a<​sub>​n</​sub>,​\\
 +b<​sub>​n-2</​sub>​ = cb<​sub>​n-1</​sub>​ + a<​sub>​n-1</​sub>,​ b<​sub>​n-3</​sub>​ = cb<​sub>​n-2</​sub>​ + a<​sub>​n-2</​sub>,​\\
 +b<​sub>​1</​sub>​ = cb<​sub>​2</​sub>​ + a<​sub>​2</​sub>,​ b<​sub>​0</​sub>​ = cb<​sub>​1</​sub>​ + a<​sub>​1</​sub>,​ r = cb<​sub>​0</​sub>​ + a<​sub>​0</​sub>//​.\\
 +Мы нашли формулы,​ по которым можно вычислять коэффициенты неполного частного //s(x)// и остаток //r//.
 +
 +__//​Литература//​__\\
 +Ананий В. Левитин. Алгоритмы:​ введение в разработку и анализ — М.: «Вильямс»,​ 2006.\\
 +Волков Е. А. Численные методы. — Учеб. пособие для вузов. — 2-е изд., испр. — М.: Наука, 1987.
others/sxema_gornera.txt · Последние изменения: 2014/11/27 09:07 (внешнее изменение)