Схема Горнера и теорема Безу. Наглядные примеры решения
Схема Горнера, теорема Безу
Пример 1. (Схема Горнера)
Представить многочлен в виде разложения по степеням (х-х0) с помощью схемы Горнера:
f(x)=x5+3x4-3x3-7x2+x+5, x0=3
Составим схему Горнера:
| 1 | 3 | -3 | -7 | 1 | 5 |
3 | 3*0+1=1 | 3*1+3=6 | 3*6+(-3)=15 | 3*15+(-7)=38 | 3*38+1=115 | 3*115+5=350 |
3 | 3*0+1=1 | 3*1+6=9 | 3*9+15=42 | 3*42+38=164 | 3*164+115=607 |
|
3 | 3*0+1=1 | 3*1+9=12 | 3*12+42=78 | 3*78+164=398 |
|
|
3 | 3*0+1=1 | 3*1+12=15 | 3*15+78=123 |
|
|
|
3 | 3*0+1=1 | 3*1+15=18 |
|
|
|
|
3 | 3*0+1=1 |
|
|
|
|
|
Получаем разложение многочлена по степеням (x-3):
f(x)=(x-3)5+18(x-3)4+123(x-3)3+398(x-3)2+607(x-3)+350Пример 2.
- г2.
Из этого выражения находим, что г = ±Л[Р + Р.
z3 + az2 + Ьх + с = 0.
Заменой х = г - это уравнение сводится к виду: 3
х3 + рх = q = 0 .
Ферро решил искать решение этого уравнения в виде х = А + В,
где а=3 - 2+г, в=3 - 2 - г.
Подставляя это выражение в уравнение (1), получим:
1 + г + 3А2В + 3АВ2 г + р(А + В) + я = 0 .
Сципион дель Ферро (1465 - 1526 гг.) -итальянский математик, открывший общий
метод решения неполного кубического уравнения
На фото вверху - математики XVI века (средневековая миниатюра)
Таким образом, исходное уравнение имеет решение х = А + В, где:
*=Иг? ■ в=■ ®
Ферро передал секрет решения уравнения (1) своему ученику Марио Фиоре. Последний, пользуясь этим секретом, стал победителем в одном из математических турниров. В этом турнире не участвовал победитель многих турниров Никколо Тарталья. Естественно, возник вопрос поединка между Тартальей и Марио Фиоре. Тарталья верил словам авторитетного математика Пич-чоли, который утверждал, что кубическое уравнение в радикалах решить невозможно, поэтому он был уверен в своей победе.
Однако за две недели до начала поединка он узнал, что Ферро нашёл решение кубического уравнения и передал свой секрет Марио Фиоре. Приложив, буквально, титанические усилия, он за несколько дней до открытия турнира получил своё решение кубического уравнения (1). 12 февраля 1535 г турнир состоялся. Каждый участник предложил своему противнику 30 задач. Проигравший должен был угостить победителя и его друзей торжественным обедом, причём количество приглашённых друзей должно было совпадать с количеством решённых победителем задач. Тарталья за два часа решил все задачи. Его противник - ни одной. Историки науки объясняют это следующим образом. Рассмотрим уравнение:
х3 + 3 х - 4 = 0 .
Это уравнение имеет единственный вещественный корень х = 1. Тогда по формуле Ферро мы получим:
х = 3/2+/5 + -л/5 .
Выражение, стоящее слева от знака равенства, должно равняться 1. Тарталья, как опытный турнирный боец, запутал своего противника такого рода иррацио-нальностями. Следует заметить, что Тарталья рассматривал только такие кубические уравнения, у которых А и В были вещественными.
Последователь Кардано, Рафаель Бомбелли, догадался, как из таких выражений получать решения кубических уравнений. Он увидел, что для данного кубического уравнения А = 2 +1, В = 2 -1. Тогда х = А + В = 4 ,
Никколо Фонтана
Тарталья (1499 - 1557 гг.) -итальянский математик
т.е. будет корнем уравнения (3). Считается, что Кардано тоже получил такого рода решения некоторых кубических уравнений.
Через некоторое время после получения формулы Тартальи, Кардано узнал решение Ферро. Он был удивлён полным совпадением решений Тартальи и Ферро. То ли потому, что Кардано узнал решение Ферро, то ли по какой-то другой причине, но в своей книге «Великое искусство» он опубликовал формулу Тартальи, правда, указав авторство Тартальи и Ферро. Узнав о выходе книги Кардано, Тарталья был смертельно обижен. И, может быть, недаром. Даже сегодня формулу (2) чаще называют формулой Кардано. Тарталья вызвал Кардано на математический поединок, но последний отказался. Вместо него вызов принял ученик Кардано, Феррари, который не только умел решать кубические уравнения, но и уравнения четвёртой степени.
Таким образом, решение уравнения четвёртой степени методом Феррари свелось к решению двух квадратных уравнений (6) и кубического уравнения (5).
Поединок Тарталья - Феррари состоялся 10 августа 1548 г. в Милане. Рассматривались уравнения третьей и четвёртой степеней. Удивительно, но Тарталья несколько задач всё-таки решил (у Феррари, наверняка, все задачи были на решение кубических уравнений с комплексными А, В и на решение уравнений четвёртой степени). Феррари решил большинство из предложенных ему задач. В итоге Тарталья потерпел сокрушительное поражение.
Практическое применение полученных решений весьма невелико. Численными методами эти уравнения решаются со сколь угодно большой точностью. Однако эти формулы внесли большой вклад в развитие алгебры и, в частности, в развитие способов решения уравнений высоких степеней. Достаточно сказать, что следующий шаг в решении уравнений был сделан только в XIX в. Абель установил, что уравнение п-ой степени при п > 5 , в общем случае, невозможно выразить в радикалах.
Всё это стало возможным в связи с появлением новой глубокой теории, а именно теории групп.
Список литературы
1. Виленкин, Н. Я. За страницами учебника математики / Н. Я. Виленкин, Л. П. Шибасов, Э. Ф. Шибасо-ва. - М. : Просвещение: АО «Учебная литература», 1996. - 320 с.
2. Гиндикин, С. Г. Рассказы о физиках и математиках / С. Г. Гиндикин. - 2-е изд. - М.: Наука, 1985. - 182 с.
ЛФХШ му&ръис мыслей
Наука только тогда благотворна, когда мы её принимаем не только разумом, но и сердцем.
Д. И. Менделеев
Вселенную нельзя низводить до уровня человеческого разумения, но следует расширять и развивать человеческое разумение, дабы воспринимать образ Вселенной по мере её открытия.
Френсис Бэкон
Примечание. В статье использованы иллюстрации с сайта http://lesequations.net
В 1505 году Сципион Феррео впервые решил один частный случай кубического уравнения. Это решение однако не было им опубликовано, но было сообщено одному ученику - Флориде. Последний, находясь в 1535 году в Венеции, вызвал на состязание уже известного в то время математика Тарталью из Брешии и предложил ему несколько вопросов, для разрешения которых нужно было уметь решать уравнения третьей степени. Но Тарталья уже нашел раньше сам решение таких уравнений и, мало того, не только одного того частного случая, который был решен Феррео, но и двух других частных случаев. Тарталья принял вызов и сам предложил Флориде также свои задачи. Результатом состязания было полное поражение Флориде. Тарталья решил предложенные ему задачи в продолжение двух часов, между тем как Флориде не мог решить ни одной задачи, предложенной ему его противником (число предложенных с обеих сторон задач было 30).
Вскоре было открыто и решение уравнений четвертой степени.
Один итальянский математик предложил задачу, для решения которой известные до той поры правила были недостаточны, а требовалось умение решать биквадратные уравнения. Большинство математиков считало эту задачу неразрешимою. Но Кардано предложил ее своему ученику Луиджи Феррари, который не только решил задачу, но и нашел способ решать уравнения четвертой степени вообще, сводя их к уравнениям третьей степени. В сочинении Тартальи, напечатанном в 1546 году, мы также находим изложение способа решать не только уравнения первой и второй степени, но и кубические уравнения, причем рассказывается инцидент между автором и Кардано, описанный выше. Сочинение Бомбелли, вышедшее в 1572 г., интересно в том отношении, что рассматривает так называемый неприводимый случай кубического уравнения, который приводил в смущение Кардано, не сумевшего решить его посредством своего правила, а также указывает на связь этого случая с классическою задачей о трисекции угла. алгебра уравнение математический
Цели:
- Систематизировать и обобщить знания и умения по теме: Решения уравнений третьей и четвертой степени.
- Углубить знания, выполнив ряд заданий, часть из которых не знакома или по своему типу, или способу решения.
- Формирование интереса к математике через изучение новых глав математики, воспитание графической культуры через построение графиков уравнений.
Тип урока : комбинированный.
Оборудование: графопроектор.
Наглядность: таблица «Теорема Виета».
Ход урока
1. Устный счет
а) Чему равен остаток от деления многочлена р n (х) = а n х n + а n-1 х n-1 + ... + а 1 х 1 + a 0 на двучлен х-а?
б) Сколько корней может иметь кубическое уравнение?
в) С помощью чего мы решаем уравнение третьей и четвертой степени?
г) Если b четное число в квадратном уравнение, то чему равен Д и х 1 ;х 2
2. Самостоятельная работа (в группах)
Составить уравнение, если известны корни (ответы к заданиям закодированы) Используется «Теорема Виета»
1 группа
Корни: х 1 = 1; х 2 = -2; х 3 = -3; х 4 = 6
Составить уравнение:
B=1 -2-3+6=2; b=-2
с=-2-3+6+6-12-18= -23; с= -23
d=6-12+36-18=12; d= -12
е=1(-2)(-3)6=36
х 4 - 2 х 3 - 23х 2 - 12 х + 36 = 0 (это уравнение решает потом 2 группа на доске)
Решение .
Целые корни ищем среди делителей числа 36.
р = ±1;±2;±3;±4;±6…
р 4 (1)=1-2-23-12+36=0 Число 1 удовлетворяет уравнению, следовательно, =1 корень уравнения. По схеме Горнера
р 3 (x) = х 3 -х 2 -24x -36
р 3 (-2) = -8 -4 +48 -36=0, х 2 =-2
р 2 (x) = х 2 -3х -18=0
х 3 =-3, х 4 =6
Ответ: 1;-2;-3;6 сумма корней 2 (П)
2 группа
Корни: х 1 = -1; х 2 = х 3 =2; х 4 =5
Составить уравнение:
B=-1+2+2+5-8; b= -8
с=2(-1)+4+10-2-5+10=15; с=15
D=-4-10+20-10= -4; d=4
е=2(-1)2*5=-20;е=-20
8+15+4х-20=0 (это уравнение решает на доске 3 группа)
р = ±1;±2;±4;±5;±10;±20.
р 4 (1)=1-8+15+4-20=-8
р 4 (-1)=1+8+15-4-20=0
р 3 (x) = х 3 -9х 2 +24x -20
р 3 (2) = 8 -36+48 -20=0
р 2 (x) = х 2 -7х +10=0 х 1 =2; х 2 =5
Ответ: -1;2;2;5 сумма корней 8(Р)
3 группа
Корни: х 1 = -1; х 2 =1; х 3 =-2; х 4 =3
Составить уравнение:
В=-1+1-2+3=1;в=-1
с=-1+2-3-2+3-6=-7;с=-7
D=2+6-3-6=-1; d=1
е=-1*1*(-2)*3=6
х 4 - х 3 - 7х 2 + х + 6 = 0 (это уравнение решает потом на доске 4 группа)
Решение.
Целые корни ищем среди делителей числа 6.
р = ±1;±2;±3;±6
р 4 (1)=1-1-7+1+6=0
р 3 (x) = х 3 - 7x -6
р 3 (-1) = -1+7-6=0
р 2 (x) = х 2 -х -6=0; х 1 =-2; х 2 =3
Ответ:-1;1;-2;3 Сумма корней 1(О)
4 группа
Корни: х 1 = -2; х 2 =-2; х 3 =-3; х 4 =-3
Составить уравнение:
B=-2-2-3+3=-4; b=4
с=4+6-6+6-6-9=-5; с=-5
D=-12+12+18+18=36; d=-36
е=-2*(-2)*(-3)*3=-36;е=-36
х 4 + 4х 3 – 5х 2 – 36х -36 = 0 (это уравнение решает потом 5 группа на доске)
Решение. Целые корни ищем среди делителей числа -36
р = ±1;±2;±3…
р(1)= 1 + 4-5-36-36 = -72
р 4 (-2) = 16 -32 -20 + 72 -36 = 0
р 3 (х) = х 3 +2х 2 -9х-18 = 0
р 3 (-2)= -8 + 8 + 18-18 = 0
р 2 (х) = х 2 -9 = 0; x=±3
Ответ: -2; -2; -3; 3 Сумма корней-4 (Ф)
5 группа
Корни: х 1 = -1; х 2 =-2; х 3 =-3; х 4 =-4
Составить уравнение
х 4 + 10х 3 + 35х 2 + 50х + 24 = 0 (это уравнение решает потом 6группа на доске)
Решение .
Целые корни ищем среди делителей числа 24.
р = ±1;±2;±3
р 4 (-1) = 1 -10 + 35 -50 + 24 = 0
р 3 (х) = x- 3 + 9х 2 + 26x+ 24 = 0
p 3 (-2) = -8 + 36-52 + 24 = О
р 2 (х) = x 2 + 7x+ 12 = 0
Ответ:-1;-2;-3;-4 сумма-10 (И)
6 группа
Корни: х 1 = 1; х 2 = 1; х 3 = -3; х 4 = 8
Составить уравнение
B=1+1-3+8=7;b=-7
с=1 -3+8-3+8-24= -13
D=-3-24+8-24= -43; d=43
х 4 - 7х 3 - 13х 2 + 43 x - 24 = 0 (это уравнение решает потом 1 группа на доске)
Решение . Целые корни ищем среди делителей числа -24.
р 4 (1)=1-7-13+43-24=0
р 3 (1)=1-6-19+24=0
р 2 (x)= х 2 -5x - 24 = 0
х 3 =-3, х 4 =8
Ответ: 1;1;-3;8 сумма 7 (Л)
3. Решение уравнений с параметром
1. Решить уравнение х 3 + 3х 2 + mх - 15 = 0; если один из корней равен (-1)
Ответ записать в порядке возрастания
R=Р 3 (-1)=-1+3-m-15=0
х 3 + 3х 2 -13х - 15 = 0; -1+3+13-15=0
По условию х 1 = - 1; Д=1+15=16
Р 2 (х) = х 2 +2х-15 = 0
х 2 =-1-4 = -5;
х 3 =-1 + 4 = 3;
Ответ:- 1;-5; 3
В порядке возрастания: -5;-1;3.
(Ь Н Ы)
2. Найти все корни многочлена х 3 - 3х 2 + ах - 2а + 6, если остатки от его деления на двучлены х-1 и х +2 равны.
Решение: R=Р 3 (1) = Р 3 (-2)
Р 3 (1) = 1-3 + а- 2а + 6 = 4-а
Р 3 (-2) = -8-12-2а-2а + 6 = -14-4а
x 3 -Зх 2 -6х + 12 + 6 = х 3 -Зх 2 -6х + 18
x 2 (x-3)-6(x-3) = 0
(х-3)(х 2 -6) = 0
3) а=0, х 2 -0*х 2 +0 = 0; х 2 =0; х 4 =0
а=0; х=0; х=1
а>0; х=1; х=а ± √а
2. Составить уравнение
1 группа . Корни: -4; -2; 1; 7;
2 группа . Корни: -3; -2; 1; 2;
3 группа . Корни: -1; 2; 6; 10;
4 группа . Корни: -3; 2; 2; 5;
5 группа . Корни: -5; -2; 2; 4;
6 группа . Корни: -8; -2; 6; 7.
2x 4 + 5x 3 - 11x 2 - 20x + 12 = 0
Для начала нужно методом подбора найти один корень. Обычно он является делителем свободного члена. В данном случае делителями числа 12 являются ±1, ±2, ±3, ±4, ±6, ±12. Начнем их подставлять по-очереди:
1: 2 + 5 - 11 - 20 + 12 = -12 ⇒ число 1
-1: 2 - 5 - 11 + 20 + 12 = 18 ⇒ число -1 не является корнем многочлена
2: 2 ∙ 16 + 5 ∙ 8 - 11 ∙ 4 - 20 ∙ 2 + 12 = 0 ⇒ число 2 является корнем многочлена
Мы нашли 1 из корней многочлена.
Корнем многочлена является 2, а значит исходный многочлен должен делиться на x - 2 . Для того, чтобы выполнить деление многочленов, воспользуемся схемой Горнера:
| 2 | 5 | -11 | -20 | 12 | |
| 2 |
В верхней строке выставляются коэффициенты исходного многочлена. В первой ячейке второй строки ставится найденный нами корень 2. Во второй строке пишутся коэффициенты многочлена, который получится в результате деления. Они считаются так:
| Во вторую ячейку второй строки запишем число 2, просто перенеся его из соответствующей ячейки первой строки. | ||||||||||||
| 2 ∙ 2 + 5 = 9 | ||||||||||||
| 2 ∙ 9 - 11 = 7 | ||||||||||||
| 2 ∙ 7 - 20 = -6 | ||||||||||||
| 2 ∙ (-6) + 12 = 0 |
Последнее число - это остаток от деления.
Если он равен 0, значит мы все верно посчитали.
2x 4 + 5x 3 - 11x 2 - 20x + 12 = (x - 2)(2x 3 + 9x 2 + 7x - 6)
Но это еще не конец. Можно попробовать разложить таким же способом многочлен 2x 3 + 9x 2 + 7x - 6.
Опять ищем корень среди делителей свободного члена. Делителями числа -6 являются ±1, ±2, ±3, ±6.
1: 2 + 9 + 7 - 6 = 12 ⇒ число 1 не является корнем многочлена
-1: -2 + 9 - 7 - 6 = -6 ⇒ число -1 не является корнем многочлена
2: 2 ∙ 8 + 9 ∙ 4 + 7 ∙ 2 - 6 = 60 ⇒ число 2 не является корнем многочлена
-2: 2 ∙ (-8) + 9 ∙ 4 + 7 ∙ (-2) - 6 = 0 ⇒ число -2 является корнем многочлена
Напишем найденный корень в нашу схему Горнера и начнем заполнять пустые ячейки:
| Во вторую ячейку третьей строки запишем число 2, просто перенеся его из соответствующей ячейки второй строки. | ||||||||||||||||||
| -2 ∙ 2 + 9 = 5 | ||||||||||||||||||
| -2 ∙ 5 + 7 = -3 | ||||||||||||||||||
| -2 ∙ (-3) - 6 = 0 |
Таким образом мы исходный многочлен разложили на множители:
2x 4 + 5x 3 - 11x 2 - 20x + 12 = (x - 2)(x + 2)(2x 2 + 5x - 3)
Многочлен 2x 2 + 5x - 3 тоже можно разложить на множители.
Для этого можно решить квадратное уравнение через дискриминант , а можно поискать корень среди делителей числа -3. Так или иначе, мы придем к выводу, что корнем этого многочлена является число -3
| Во вторую ячейку четвертой строки запишем число 2, просто перенеся его из соответствующей ячейки третьей строки. | ||||||||||||||||||||||||
| -3 ∙ 2 + 5 = -1 | ||||||||||||||||||||||||
| -3 ∙ (-1) - 3 = 0 |
Таким образом мы исходный многочлен разложили на линейные множители.
Решение уравнений высших степеней – история полная драматизма, разочарования и радости открытия. В течение почти 700 лет математики разных стран пытались найти приёмы решения уравнений третьей, четвёртой и более высоких степеней.
Со времен Омара Хайяма ученые средневековья почти 400 лет искали формулу для решения уравнений третьей степени.
Паоло Вальмес за свое открытие поплатился жизнью. Инквизиция отправила Вальмеса на костер. Однако трагедии и неудачи не смогли остановить прогресс.
Омар Хайям(1048 – 1123)
В своих математических трудах таджикский ученый описал все возможные виды уравнений третьей степени и рассмотрел геометрический способ их решения.
Николо Тарталья (1499 – 1557)
Решил уравнение в радикалах
Джероламо Кардано(1501 – 1576)
Обобщил приемы решения разных видов кубических уравнений. Независимо от Тартальи открыл формулу корней («формула Кардано»).
Франсуа Виет (1540 – 1603)
Установил, каким образом корни уравнения выражаются через коэффициенты.
Поставил вопрос о существовании решения уравнений произвольных степеней в радикалах
Паоло Руффини (1765 – 1822)
Пытался доказать невозможность алгебраического решения общих уравнений выше четвертой степени.
Жозеф Луи Лагранж (1736 – 1813)
Искал признаки уравнений высших степеней, разрешимых в радикалах
Нильс Хенрик Абель (1802 – 1829)
Доказал неразрешимость в радикалах уравнения пятой степени и более высоких степеней в общем случае.
Эварист Галуа (1811 – 1832)
Нашел необходимое и достаточное условие, которому удовлетворяет алгебраическое уравнение, разрешимое в радикалах.
2)[/математика]
Основные авторы: Алексей Фролов.
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.1.1 Постановка задачи
- 1.1.2 Общая схема
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1. 4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Серийная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс распараллеливания алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 1.1 Общее описание алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Возможные методы и соображения для параллельной реализации алгоритма
- 2.3 Результаты выполнения
- 2.4 Выводы для разных классов компьютерной архитектуры
- 3 Каталожные номера
4 Макроструктура алгоритма1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
1.1.1 Постановка задачи
Схема Горнера посвящена делению полинома [math]P_n(x)[/math] с известные коэффициенты биномом [math]x - \alpha[/math]. Результатами этой операции являются коэффициенты многочлена [math]Q_{n - 1}(x)[/math], полученные по соотношению
- [математика]P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x)[/math]
и значение [math]P_n(\alpha) [/math] многочлена [math]P_n(x)[/math] в заданной точке [math]\alpha[/math].
К сожалению, метод Хорнера часто сводится только к вычислению полинома [math]P_n(x)[/math] в точке [math]\alpha[/math].
1.1.2 Общая схема
Фактически схема Горнера реализует деление полинома в длину на бином [math]x - \alpha[/math]. По теореме Безу остаток этой операции равен значению многочлена [math]P_n(x)[/math] в точке [math]\alpha[/math].
1.2 Математическое описание алгоритма
Входные данные: одномерный массив, состоящий из [math]n + 1[/math] чисел [math]a_k[/math] и скаляр [math]\alpha[/math ].
Выходные данные: одномерный массив, состоящий из [math]n + 1[/math] чисел [math]b_k[/math].
Формулы метода Горнера основаны на соотношении
- [математика]P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x)[/math].
Теперь представим приведенные выше многочлены в канонической форме: 9{n - 2} + \dots + b_{n - 2} x + b_{n - 1}. \end{выравнивание} [/math]
Через [math]b_n[/math] мы обозначаем [math]P_n(\alpha)[/math].
Подставляя эти многочлены в их каноническом виде в приведенное выше соотношение и приравнивая коэффициенты при равных степенях [math]x[/math], приходим к следующим формулам схемы Горнера:
- [математика] \начать{выравнивать} б_0 & = а_0, \\ b_k & = a_k + \alpha b_{k - 1}, \quad k = 1, \dots, n. \end{выравнивание} [/math]
1.3 Вычислительное ядро алгоритма
Вычислительное ядро алгоритма Горнера в его последовательной версии можно представить в виде последовательного набора [math]n[/math] «двойных» операций: умножения элементов выходного массива на один и тот же скаляр и сложения результата к следующему элементу входного массива.
1.4 Макроструктура алгоритма
Из вычислительного ядра алгоритма Горнера следует, что его основная часть состоит из последовательного набора указанных выше «двойных» операций.
1.5 Схема реализации последовательного алгоритма
Формулы алгоритма описаны выше. Операции выполняются в порядке возрастания [math]k[/math].
1.6 Последовательная сложность алгоритма
Для многочлена степени [math]n[/math] количество умножений равно [math]n[/math], количество сложений также равно [math ]n[/математика]. Следовательно, алгоритм Горнера имеет линейную сложность по количеству последовательных операций.
1.7 Информационный граф
Граф алгоритма показан на рис.1 для [math]n = 9[/math]. Как видно, график последовательный.
Рис. 1. Схема Горнера: серийный вариант.
Здесь аббревиатуры In (Input) и Out (Output) используются для обозначения первого коэффициента входного массива и значения полинома в заданной точке [math]\alpha[/math] соответственно. Через Op мы обозначаем «двойную» операцию: умножение входной переменной на скаляр и прибавление результата к другой переменной.
1.8 Ресурс распараллеливания алгоритма
Последовательная версия алгоритма Хорнера не имеет ресурса распараллеливания. Его параллельная форма состоит из одного слоя и совпадает с последовательным алгоритмом.
Таким образом, высота параллельной формы равна [math]n[/math] умножений плюс [math]n[/math] сложений. Следовательно, этот алгоритм имеет линейную сложность относительно высоты параллельной формы. Ширина параллельной формы равна [math]1[/math]; следовательно, этот алгоритм имеет постоянную сложность относительно ширины параллельной формы.
1.9 Входные и выходные данные алгоритма
Входные данные: массив [math]a[/math] (его элементы обозначаются [math]a_i[/math], где [math]i = 0, \dots , n[/math]) и скаляр [math]\alpha[/math].
Дополнительные ограничения: отсутствуют.
Количество входных данных: [math]n + 2[/math].
Выходные данные: массив [math]b[/math] (его элементы обозначаются [math]b_k[/math], где [math]k = 0, \dots, n[/math])
Количество выходных данных: [math]n + 1[/math].
1.10 Свойства алгоритма
В случае неограниченных ресурсов компьютера отношение последовательной сложности к параллельной сложности равно константе (1).
Вычислительная мощность алгоритма, рассматриваемая как отношение количества операций к общему количеству входных и выходных данных, равна 1 (количество входных и выходных данных даже больше на 1, чем количество операций). Алгоритм полностью детерминирован. Дуги информационного графа локальны. Устойчивость схемы Горнера оптимальна для вычисления значений многочлена с известным коэффициентом.
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
Схема Горнера может быть представлена на Фортране в виде
б(0) = а(0) ДО I = 1, Н б(I) = а(I)+b(I-1)*альфа КОНЕЦ ДЕЛАТЬ
2.2 Возможные методы и соображения для параллельной реализации алгоритма
Этот алгоритм не предназначен для параллельной реализации.
Помимо приведенной выше простейшей реализации, существуют более примитивные коды, реализующие только часть схемы Горнера. Это можно объяснить тем, что во многих случаях необходимо знать значение многочлена (остаток от деления), но необязательно знать только частное многочлена с отброшенным остатком.
В таких случаях вместо всех элементов массива [math]b[/math] следует использовать один и тот же скаляр.
2.3 Результаты выполнения
2.4 Выводы для различных классов компьютерной архитектуры
3 Ссылки
Полиномы - Использование метода Хорнера
спросил
Изменено 4 года, 1 месяц назад
Просмотрено 34к раз
9{n-1}+\cdots+a_1x+a_0,$$ вы можете думать о $p(x)$ во вложенной форме как $p_0$, где $p_n=a_n$ и $p_{k-1}=p_kx+a_ {к-1}$. То есть начните со старшего коэффициента ($a_n$). Умножьте на $x$ и добавьте следующий коэффициент (добавляя ноль для заполнения «недостающих» степеней $x$), повторяя до тех пор, пока не добавите постоянный член ($a_0$). Вернемся к тому же примеру: $$\begin{выравнивание} p_7&=6\\ р_6&=(6)х+0\\ p_5&=((6)x+0)x-7\\ p_4&=(((6)х+0)х-7)+2\\ p_3&=((((6)х+0)х-7)+2)х+0\\ p_2&=(((((6)x+0)x-7)+2)x+0)-10\\ p_1&=((((((6)x+0)x-7)+2)x+0)-10)+20\\ p_0&=(((((((6)x+0)x-7)+2)x+0)-10)+20)-6 \end{выравнивание}$$ 92 + x - 5$ для $x = 3$.