Методи знаходження коренів поліномів

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

СУМСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ

КАФЕДРА ІНФОРМАТИКИ

Контрольна робота

З чисельних методів

на тему:

"Метод и знаходження коренів поліномів"

Суми - 2007 р.

План

1 Знаходження коренів рівнянь ()

2 Схема Горнера

3 Функції довільного виду

4 Знаходження коренів поліномів

Список використовуваних інформаційних джерел

1 Знаходження коренів рівнянь ()

Одним з найбільш поширених методів пошуку коренів рівнянь є метод Ньютона і його модифікації. Нехай потрібно вирішити рівняння . Будемо вважати, що x є рішенням рівняння. Розкладемо функцію f (x) в ряд в точці x 0 близькою до точки x і обмежимося тільки першими двома членами розкладання.

Оскільки x - корінь рівняння, то . Отже,

Таким чином, якщо нам відомо наближене значення кореня рівняння, то отримане рівняння дозволяє його уточнити. Зрозуміло, що процес уточнення можна повторювати багаторазово, до тих пір, поки значення функції не будуть відрізнятися від нуля на величину меншу, ніж задана точність пошуку. Чергове k-е наближення знаходиться за формулою

Обмежившись в розкладанні тільки першими двома членами, ми фактично замінили функцію f (x) на пряму лінію, дотичну в точці x 0, тому метод Ньютона ще називають методом дотичних. Далеко не завжди буває зручно знаходити аналітичний вираз для похідної функції. Проте, в цьому і немає особливої ​​необхідності: оскільки на кожному кроці ми отримуємо наближене значення кореня, можна для його обчислення використовувати наближене значення похідної.

Як малої величини можна взяти, наприклад, задану точність обчислень , Тоді розрахункова формула набуде вигляду

15

З іншого боку, для обчислення похідної можна скористатися значеннями функції, отриманими на двох попередніх кроках,

15

У такому вигляді метод називається методом січних (secant method). При цьому, однак, виникає проблема з обчисленням першого наближення. Зазвичай вважають, що , Тобто перший крок обчислень проводиться з використанням формули, а всі наступні - з використанням формули. Саме ця обчислювальна схема реалізована в пакеті Mathcad. Використовуючи метод січних, ми не можемо гарантувати, що корінь знаходиться між двома останніми наближеннями. Можна, однак, для обчислення чергового наближення використовувати межі інтервалу, на якому функція змінює знак. Такий метод називається методом хорд (false position method).

Ідея методу січних розвивається в методі Мюллера. Однак у цьому методі для знаходження чергового наближення використовуються три попередні точки. Іншими словами, метод використовує не лінійну, а квадратичну інтерполяцію функції. Розрахункові формули методу такі ^1:

15

15

Знак перед коренем вибирається так, щоб абсолютне значення знаменника було максимальним.

Оскільки пошук кореня закінчується, коли виконається умова , То можлива поява помилкових коренів. Наприклад, для рівняння помилковий корінь з'явиться в тому випадку, якщо точність пошуку задана менше, ніж 0,0001. Збільшуючи точність пошуку, можна позбутися хибних коренів. Однак не для всіх рівнянь такий підхід працює. Наприклад, для рівняння , Яке, очевидно, не має дійсних коренів, для будь-якої, як завгодно малої точності знайдеться значення x, що задовольняє умовою закінчення пошуку. Наведені приклади показують, що до результатів комп'ютерних обчислень завжди потрібно ставитися критично, аналізувати їх на правдоподібність. Щоб уникнути "підводних каменів" при використанні будь-якого стандартного пакета, що реалізує чисельні методи, потрібно мати хоча б мінімальне уявлення про те, який саме чисельний метод реалізований для вирішення того чи іншого завдання.

У тому випадку, коли відомий інтервал, на якому розташований корінь, можна скористатися іншими методами знаходження рішення рівняння.

У методі Ріддера (Ridder 's method) обчислюють значення функції в середині інтервалу . Потім шукають експоненційну функцію таку, що Потім застосовують метод хорд, використовуючи значення . Чергове значення обчислюють за формулою

15

Метод Брента (Brent method) з'єднує швидкість методу Ріддера і гарантовану збіжність методу розподілу відрізка навпіл. Метод використовує зворотний квадратичну інтерполяцію, тобто шукає x як квадратичну функцію y. На кожному кроці перевіряється локалізація кореня. Формули методу досить громіздкі і ми не будемо їх наводити.

Особливі методи застосовують для пошуку коренів полінома. У цьому випадку можуть бути знайдені всі корені. Після того як один з коренів полінома знайдений, ступінь полінома може бути знижена, після чого пошук кореня повторюється.

Метод Лобачевського, метод наближеного (чисельного) рішення алгебраїчних рівнянь, знайдений незалежно один від одного бельгійським математиком Ж. Данделеном, російським математиком Н. І. Лобачевським (в 1834 у найбільш досконалій формі) і швейцарським математиком К. Греффе. Суть Л. м. полягає в побудові рівняння f 1 (x) = 0, коріння якого є квадратами коренів вихідного рівняння f (x) = 0. Потім будують рівняння f 2 (x) = 0, коренями якого є квадрати коренів рівняння f 1 (x) = 0. Повторюючи цей процес кілька разів, отримують рівняння, корені якого сильно розділені. У разі якщо всі корені вихідного рівняння дійсні і різні за абсолютною величиною, є прості обчислювальні схеми Л. м. для знаходження наближених значень коренів. У разі рівних за абсолютною величиною коренів, а також комплексних коренів обчислювальні схеми Л. м. дуже складні.

Метод Лагера (Laguerre 's method) грунтується на таких пропорціях для поліномів

Припускають, що корінь x 1 знаходиться на відстані a від поточного наближення, в той час як всі інші корені знаходяться на відстані b: . Тоді

,

звідки

Знак перед коренем вибирають з таким розрахунком, щоб отримати найбільше значення знаменника.

Ще один метод, який застосовують для пошуку коренів поліномів, - метод супроводжує матриці (companion matrix). Можна довести, що матриця

,

звана супроводжує матрицею для полінома , Має власні значення рівні коріння полінома. Нагадаємо, що власними значеннями матриці називаються такі числа , для яких виконується рівність або . Існують досить ефективні методи пошуку власних значень, про деякі з них ми будемо говорити далі. Таким чином, завдання пошуку коренів полінома можна звести до задачі пошуку власних значень супроводжує матриці.

2 Схема Горнера

Обчислення за схемою Горнера виявляється більш ефективним, причому воно не дуже ускладнюється. Ця схема полягає в наступному поданні многочлена:

p (x) = ((... ((anx + an-1) x + an-2) x + ... + a2) x + a1) x + a0.

Займемося загальним многочленом види:

p (x) = anxn + an-1xn-1 + an-2xn-2 + ... + a2x2 + a1x + a0.

Ми будемо припускати, що всі коефіцієнти an, ..., a0 відомі, постійні і записані у масив. Це означає, що єдиним вхідним даними для обчислення многочлена служить значення x, а результатом програми має бути значення многочлена в точці x.
Стандартний алгоритм обчислення прямолінійний:

Evaluate (x)

xточка, в якій обчислюється значення многочлена

result = a [0] + a [1] * x

xPower = x

for i = 2 to n do

xPower = xPower * x

result = result + a [i] * xPower

end for

return result

Цей алгоритм абсолютно прозорий і його аналіз очевидний. У циклі for міститься два множення, що виконуються n - 1 раз. Крім того, одне множення виконується перед циклом, тому загальне число множень одно 2n - 1. У циклі виконується також одне додавання, і одне додавання виконується перед циклом, тому загальне число додавань одно n.

Ви можете легко перевірити, що це подання задає той же многочлен, що й вище. Відповідний алгоритм виглядає так:

HornersMethod (x)

xточка, в якій обчислюється значення многочлена

for i = n - 1 down to 0 do

result = result * x

result = result + a [i]

end for

return result

Цикл виконується n разів, причому всередині циклу є одне множення і одне додавання. Тому обчислення за схемою Горнера вимагає n множення і n складань - дворазове зменшення числа множень порівняно зі стандартним алгоритмом.

Попередня обробка коефіцієнтів

Результат можна навіть поліпшити, якщо обробити коефіцієнти многочлена до початку роботи алгоритму. Основна ідея полягає в тому, щоб висловити многочлен через многочлени меншою мірою. Наприклад, для обчислення значення x256 можна скористатися таким же циклом, як і у функції Evaluate на початку цієї статті, у результаті буде виконано 255 множень. Альтернативний підхід полягає в тому, щоб покласти result = x * x, а потім сім разів виконати операцію result = result * result. Після першого виконання мінлива result буде містити x4, після другого x8, після третього x16, після четвертого x32, після п'ятого x64, після шостого x128, і після сьомого x256.

Для того, щоб метод попередньої обробки коефіцієнтів працював, потрібно, щоб многочлен був унімодальних (тобто старший коефіцієнт an повинен дорівнювати 1), а ступінь многочлена повинна бути на одиницю менше деякої міри двійки (n = 2k - 1 для деякого k> 1) . У такому випадку многочлен можна представити у вигляді:

p (x) = (xj + b) q (x) + r (x), де j = 2k-1. (1)

В обох многочленів q і r буде вдвічі менше членів, ніж в p. Для отримання потрібного результату ми обчислимо окремо q (x) і r (x), а потім зробимо одне додаткове множення і два складання. Якщо при цьому правильно вибрати значення b, то обидва многочлена q і r виявляються унімодальних, причому ступінь кожного з них дозволяє застосувати до кожного з них ту ж саму процедуру. Ми побачимо, що її послідовне застосування дозволяє заощадити обчислення.

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

p (x) = x7 + 4x6 - 8x4 + 6x3 + 9x2 + 2x - 3.

Визначимо спочатку множник xj + b в рівнянні (1). Ступінь многочлена p дорівнює 7, тобто 23 - 1, тому k = 3. Звідси випливає, що j = 22 = 4. Виберемо значення b таким чином, щоб обидва многочлена q і r були унімодальних. Для цього потрібно подивитися на коефіцієнти aj-1 в p і покласти b = aj-1 - 1. У нашому випадку це означає, що b = a3 - 1 = 5. Тепер ми хочемо знайти значення q і r, що задовольняють рівнянню:

x7 + 4x6 - 8x4 + 6x3 + 9x2 + 2x - 3 = (x4 + 5) q (x) + r (x).

Многочлени q і r збігаються відповідно з приватним і залишком від ділення p на x4 + 5. Розподіл із залишком дає:

p (x) = (x4 + 5) (x3 + 4x2 + 0x + 8) + (x3 - 11x2 + 2x - 37).

На наступному кроці ми можемо застосувати ту ж саму процедуру до кожного з многочленів q і r:

q (x) = (x2 - 1) (x + 4) + (x + 12), r (x) = (x2 + 1) (x - 11) + (x - 26).

В результаті отримуємо:

p (x) = (x4 + 5) ((x2 - 1) (x + 4) + (x + 12)) + ((x2 + 1) (x - 11) + (x - 26)).

Подивившись на цей многочлен, ми бачимо, що для обчислення x2 потрібно одне множення; ще одне множення необхідно для підрахунку x4 = x2 * x2. Крім цих двох множень в обчисленні правій частині рівності беруть участь ще три множення. Крім того, виконується 10 операцій додавання. У таблиці 1 наведені порівняльні результати аналізу цього методу та інших методів обчислення. Економія не виглядає значною, проте це пояснюється тим, що ми розглядаємо лише окремий випадок. Загальну формулу для складності можна вивести, уважно вивчивши процедуру. Зауважимо насамперед, що в рівності (1) беруть участь одне множення і два складання. Тому для числа множень M = M (k) і числа складань A = A (k) ми отримуємо наступний набір рекурентних співвідношень:

Таблиця 1. Число операцій при обчисленні значення многочлена ступінь 7

Вирішуючи ці співвідношення, ми робимо висновок, що число множень приблизно дорівнює N / 2, а число додавань приблизно дорівнює (3N - 1) / 2. Неврахованими, однак, залишилися множення, необхідні для підрахунку послідовності значень x2, x4, x8, ..., x2k-1; на це потрібно додатково k - 1 множення. Тому загальна кількість множень приблизно дорівнює N / 2 + log2N.

Таблиця 2. Число операцій при обчисленні значення многочлена ступеня N

У таблиці 2 наведені результати порівняльного аналізу стандартного алгоритму, схеми Горнера і алгоритму з попередньою обробкою коефіцієнтів. При порівнянні останніх двох алгоритмів видно, що нам вдалося заощадити N / 2 - log2N множень, але за рахунок додаткових (N - 1) / 2 складань. У всіх існуючих обчислювальних системах обмін множень на складання вважається вигідним, тому попередня обробка коефіцієнтів підвищує ефективність.

3 Функції довільного виду

Знайдемо нулі функції на інтервалі x = [-2,7], використовуючи Mathcad

Зобразимо спочатку функцію на графіку.

На заданому інтервалі функція три рази звертається в нуль. Визначимо нулі функції, використовуючи вбудовану функцію root (f (x), x). Перший аргумент - функція, нуль якої необхідно знайти, другий - змінна, яку необхідно варіювати. (Взагалі кажучи, функція f може бути функцією багатьох змінних і необхідно вказувати, за якою саме змінної ми шукаємо нуль функції.) Крім того, необхідно задати початкове наближення пошуку. Точність обчислень задається вбудованої змінної TOL. За замовчуванням її значення дорівнює 0,001. Це значення можна змінити або через меню Math / Built-In Variables або безпосередньо в тексті документа:

Задаємо початкове наближення:

І обчислюємо корінь:

Якщо потрібно знайти кілька коренів, як в нашій задачі, то має сенс визначити нову функцію:

Функція r (x) повертає значення кореня найближче до x ^2, тобто початкове наближення ми задаємо через аргумент функції. Задаємо вектор початкових наближень x і знаходимо відповідні їм коріння X:

Для даного прикладу коріння легко можуть бути знайдені аналітично. Вони рівні на заданому інтервалі   / 2    / 2 і       Отриманий чисельний результат з заданою точністю збігається з точним рішенням.

Визначення нової функції доцільно й у тому випадку, коли ми хочемо дослідити залежність рішення від параметра. Нехай функція залежить від параметра a

Перший аргумент функції z задає значення параметра, другий - початкове наближення. Знайдемо коріння рівняння при значеннях параметра 1 і 2.

Якщо ми хочемо отримати комплексний корінь, то початкове наближення слід задавати комплексним:

4 Знаходження коренів поліномів

Для знаходження коренів поліномів є вбудована функція polyroots (a). Аргументом функції є вектор коефіцієнтів полінома , Тобто для рівняння вектор а має вигляд

Якщо в поліномі відсутні деякі міри, то на відповідних місцях слід писати 0. Нехай потрібно знайти корені полінома

Коефіцієнти полінома можуть бути і комплексними.

Список використовуваних інформаційних джерел

1. Coppersmith D., Odlyzko AM, Schroeppel R. Descrete logarithms in GF (p) / / Algorithmica. V. 1,1986. P. 1-15.

2. Lenstra A. K, Lenstra HW (jr.) The Development of the Number Field Siev. Lect. Notes in Math. V. 1554. Springer, 1993.

3. McCarthy DP "The optimal algorithm to evaluate xn using elementary multiplication methods", Math. Comp., Vol. 31, no 137, 1977, pp. 251 - 256.