Claw.ru | Рефераты по математике | Вычисление многочленов — от Ньютона до наших дней Вычисление многочленов — от Ньютона до наших дней | Категория реферата: Рефераты по математике | Теги реферата: реферат на тему здоровье, дипломная работа 2011 | Добавил(а) на сайт: Jejler. Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

Условимся обозначать уравнение системы (IV) с номером j (1≤j≤2k) через (IV)-j. Тогда процесс решения системы (IV) можно описать в нескольких словах: A1 выражается через a1 из (IV)-1 и (I), A2 выражается через a1, a2 и b из (IV)-2, A3 выражается через a1, a2, a3 и b из (IV)-3 и т.д. Последним из уравнения (IV)-(2k–2) мы выразим неизвестное A2k–2; затем, подставив в уравнение (IV)-(2k–1) найденные выражения для A2k–2 и A2k–3, мы получим уравнение относительно b.

Лемма 2. Неизвестные A2j–1 и A2j выражаются из системы (IV) через параметр b и коэффициенты a1, a2, ..., a2k–2; согласно формулам (b1 выражается через a1 согласно (I))

A2j–1 = (–1)j–1[(k – j)b1 + 1]bj–1 + + S1,j(a1, a2, a3)bj–2 + ... + Sj–1,j(a1, a2, ..., a2j–1),	(V)
A2j = (–1)jbj + T1,j(a1, a2)bj–1 + ... + Tj,j(a1, a2, ..., a2j).	(VI)

Доказательство. База индукции: j=1, A1 = a1 – b1 = [(k – 1)b1 + 1]b,  A2 = –b + T1,1(a1, a2).

Посылка индукции — формулы (V), (VI) при 1≤j0 всегда имеет хотя бы один корень. Несмотря на то, что при n≥5 формул для нахождения этого корня и не существует, разработаны методы нахождения всех корней многочлена с любой точностью.

Начиная с третьей строки, схема (7.k) очень напоминает схему Горнера(3); разница лишь в том, что теперь после каждого умножения степень увеличивается не на единицу, а на два.

Итак, нам удалось уменьшить число умножений по сравнению со схемой Горнера вдвое. Какой ценой? Из решения упражнения 5 видно, что процесс вычисления параметров b1, b2, ..., b2n по коэффициентам a1, a2..., a2n очень сложен, — он включает в себя решение серии уравнений с одним неизвестным степени k–1, k–2, ... Это означает, в частности, что при k≥6 (n≥12) формул вычисления параметров нет4 , хотя, разумеется, их значения могут быть найдены приближёнными методами с любой степенью точности.

Здесь возникает ещё одно затруднение, оказавшееся, правда, преодолимым. До сих пор мы не уточняли, значения каких — действительных или комплексных — многочленов мы вычисляем. Схема Горнера применима и в том, и в другом случае, схема же (7.k) преимущественно «комплексная» — действительным коэффициентам могут соответствовать комплексные параметры. Появление комплексных чисел при вычислении действительных многочленов намного увеличивает число арифметических операций5 . К счастью, в 1960году схему (7.k) небольшим усложнением удалось превратить в действительную; однако полные доказательства в этом случае уже очень непросты.

§6. О схемах вообще...

 — Минуточку, минуточку — раздались протестующие голоса. — Избегайте, пожалуйста, научных терминов, объясняйте популярно...

— Верно! — подтвердили остальные. — Говорите понятнее... Что такое лес?

Я. Осенка. Загородная прогулка в 2050 году

Пришло время спросить, нет ли схем, более экономных, чем схема (7.k)? Но тогда неизбежен и вопрос — что такое схема?

Определение. (I). Схема с предварительной обработкой коэффициентов — это последовательность арифметических операций, в которых участвуют переменная x, параметры b1, b2, ..., bm и результаты предшествующих операций. Результат последней операции назовем результатом схемы. (II). Если при некотором наборе значений параметров b1, ..., bm результат схемы есть данный многочлен степени n, то мы скажем, что схема представляет этот многочлен. (III). Если схема представляет многочлен, то процесс вычисления по его коэффициентам соответствующего набора значений параметров назовем предварительной обработкой коэффициентов. (IV). Схема называется универсальной степени n, если она представляет любой многочлен степени n вида (1).

Примеры. 1. Схема (7.k) — универсальная (степени n=2k); то же верно и для схемы Горнера (параметры — сами коэффициенты).

2. Схема p(x) = (xn+1 – b1)/(x – b2) представляет многочлен (в) §3 при b1 = b2 = 1.

Упражнение6. Докажите, что общее число SN схем (всех степеней), содержащих не более N операций, конечно и не превосходит числа6   [(3N – 1)!/(2N – 1)!]2.

Решение

Так как в каждой операции участвует не более двух параметров, то общее число параметров в схеме с N операциями не больше 2N–1 (хотя бы в одной операции должна участвовать переменная x). В первой операции участвуют два числа. Каждое из них есть либо x, либо один из не более чем 2N–1 параметров; всего не более (2N)2 возможностей. Во второй операции могут участвовать те же числа и результат первой операции; всего не более (2N+1)2 возможностей, и так далее. Наконец, в последней операции могут участвовать не более 3N–1 чисел (в том числе N–1 результат предыдущих операций); всего не более (3N–1)2 возможностей. Общее число различных вариантов не больше произведения этих чисел, то есть

SN ≤ (2N)2 (2N + 1)2 ... (3N – 1)2 = [(3N – 1)!/(2N – 1)!]2.

§7. ... И о наилучшей из них, в частности

Положение, в котором мы находимся, заставляет нас прибегать ко всестороннему изучению предмета.

Платон

Рекомендуем скачать другие рефераты по теме: тесты для девочек, анализ темы курсовой работы.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата