Приближённые на методи вирішення алгебраического уравнения

Міністерство науку й освіти Украины.

Дніпропетровський Національний Университет.

Радіофізичний факультет.

Кафедра фізики СВЧ.

Реферат за курсом про чисельні методов:

«Приближённые на методи вирішення алгебраичекого уравнения».

Выполнил: Студент групи РЭ-01−1.

Проверил: Доцент кафедри фізики СВЧ.

До. У. Заболотный.

Дніпропетровськ 2002.

1. Кількісна рішення рівняння, умови, накладені на функцію, графічний метод визначення корней.

2. Метод дихотомии.

3. Метод итераций.

4. Швидкість збіжності процесу итераций.

5. Метод касательных.

6. Перші наближення для методу касательных.

7. Метод секущих.

8. Метод хорд.

9. Удосконалений метод хорд 10. Комбінований метод рішення рівняння 11. Прикінцеві зауваження 12. Список використаної литературы.

1. Кількісна рішення рівнянь з однією неизвестным.

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

f (x)=0 (1.1).

на заданому відрізку [a, b].

Рівняння називається алгебраїчним, якщо задана функція є поліном n-ой степени:

f (x) = P (x) = a0xn + a1xn- 1 + … + an-1 x + an = 0, a0 (0.

Вимога a0 (0 обов’язково, бо за невиконанні цього умови дане рівняння буде порядок ниже.

Будь-яке рівняння (1.1) називається трансцендентним, тоді як ньому неможливо явно знайти невідоме, а можна лише приближённо.

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

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

Коренем рівняння (1.1) називається така кількість (, де f (()=0.

При визначенні приближённых коренів рівняння (1.1) необхідно вирішити дві задачи:

1) відділення коренів, т. е. визначення досить малих проміжків, у кожному у тому числі заключён сам і лише одне корінь уравнения.

(простий і кратный);

2) уточнення коренів із заданою точністю (вірним числом знаків до чи помирають після запятой);

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

Друге завдання вирішується у методах розглянутих ниже.

При графічному відділенні коренів рівняння (1.1) потрібно останнє перетворити до виду:

(1(x)=(2(x) (2.1).

и побудувати графіки функцій y1=(1(x), y2=(2(x).

Справді, корінням рівняння (1.1).

f (x) = (1(x) — (2(x) = 0.

являются абсциссы точок перетину цих графіків (і лише они).

З усіх способів, якими можна рівняння (1.1) перетворити до виду (2.1) вибираємо той, що забезпечує найбільш просте побудова графіків y1=(1(x) і y2=(2(x). Зокрема можна взяти (2(x) = 0 і тоді прийдемо побудувати графіка функції (1.1), точки перетину якого з прямий y2=(2(x)=0, т. е. з віссю абсцис, це і є шукані коріння рівняння (1.0).

Умови, накладені на функцію f (x) на відрізку [a, b].

Будемо припускати, що функція f (x) безупинна на відрізку [a, b] (для методу хорд можна зажадати на інтервалі) і має цьому інтервалі першу і другу похідні, причому обидві вони знакопостоянны (в частковості відмінні від нуля). Будемо також припускати, що функція f (x) приймає на кінцях відрізка значення різного знака. З огляду на знакопостоянства першої похідною функція f (x) суворо монотонна, тому при зроблених припущеннях рівняння (1.1) має у точності один корінь на интервале.

(a, b).

2. Метод дихотомии.

Цей метод ще називається методом вилки.

Маємо знайти корінь рівняння (1.1) на відрізку [a, b]. Розглянемо відрізок [x0, x1]: [x0, x1]([a, b]. Нехай ми знайшли такі точки х0, х1, що f (х0) f (х1) (0, т. е. на відрізку [х0, х1] лежить щонайменше одного кореня рівняння. Знайдемо середину відрізка х2=(х0+х1)/2 і обчислимо f (х2). Із двох половинок відрізка виберемо ту, на яку виконується умова f (х2) f (хгран.) (0, оскільки одне із коренів лежить на жіночих цієї половині. Потім новий відрізок ділимо навпіл і виберемо ту половину, на кінцях якої функція має різні знаки, тощо. буд. (рис 1.2).

Якщо потрібно знайти корінь з точністю Є, то продолжаем розподіл навпіл до того часу, поки довжина відрізка стане менше 2Е. Тоді середина останнього відрізка дасть значення кореня з необхідної точностью.

Дихотомія проста і дуже надёжна. До простому корені вона сходиться для будь-яких безперервних функцій зокрема і дифференцируемых; цьому вона підвалиначива до помилок округлення. Швидкість збіжності не велику; за ітерацію точність збільшується прикладале вдвічі, т. е. уточнення трьох цифр вимагає 10 ітерацій. Зате точність відповіді гарантується. рис. 1.2.

Приступимо до доведенню те, що якщо безперервна функція приймає на кінцях деякого відрізка [a, b] значення різних знаків, то методом дихотомії однозначно буде знайдено корень.

Припустимо для определённости, що функція f (x) приймає на лівому кінці відрізка [a, b] негативного значення, але в правом — положительное:

f (a) < 0, f (b) > 0.

Візьмемо середню точку відрізка [a, b], h=(a+b)/2 і обчислимо значення у ній функції f (x). Якщо f (h)=0, то твердження теореми доведено: ми знайшли цієї точки, де функція звертається до нуль. Якщо f (h)(0, тоді з відрізків [a, h] і [h, b] виберемо них той, де функція з його кінцях приймає значення різних знаків. Означимо його [a1, b1]. За побудовою: f (a1)0. Потім середню точку відрізка [a1, b1] точку h1 і проведемо хоча б алгоритм перебування іншого відрізка [a2, b2] у якому з побудови f (a2)0. Будемо продовжувати той процес. Через війну вона або оборвётся на деякому кроці n через те, що f (hn)=0, або перебуватиме тривати необмежено. У першому випадку питання існуванні кореня рівняння f (x)=0 вирішене, тому розглянемо другий случай.

Необмежене продовження процесу дає послідовність відрізків [a, b], [a1, b1], [a2, b2],… Ці відтинки вкладено один у друга — кожну наступну відрізок належить всім предыдущим:

an (an+ 1 < bn+ 1 (bn (1.2) причём:

f (an) < 0, f (bn) > 0.

Довжини відрізків зі зростанням номери n прагнуть нулю:

[pic].

Розглянемо ліві кінці відрізків. Відповідно до (1.2) вони утворюють монотонно убутну обмежену послідовність {an}. Така послідовність має межа, що можна позначити через c1: [pic].

Согласно (1.1) і теоремі перехід до межі в неравенствах имеем:

c1 (bn (2.2).

Тепер на праві кінці відрізків. Вони утворюють монотонно не зростання обмежену послідовність {bn}, що має межа. Означимо його через с2: [pic]. Відповідно до нерівності (2.1) межі с1 і с2 задовольняють нерівності с1 (с2. Отже, an (с1 < с2 (bn, і следовательно:

с2-с1 (bn — an=(b-a)/2n.

Отже, різницю с2-с1 менше будь-якого наперед заданого позитивного числа. Це означає, що с2-с1=0, т. е.: с1=с2=с.

Знайдена точка цікава тим, що вона єдина загальної точкою всім відрізків побудованої послідовності Використовуючи безперервність функції f (x), доведемо, що вона є коренем рівняння f (x)=0.

Ми знаємо, що f (an)0, те що її досягти досить зробити число кроків N, не що перевищує log2[(b-a)/(]: N>log2[(b-a)/(].

3. Метод итераций.

Цей метод називається ще методом послідовних приближений.

Нехай слід знайти корінь рівняння (1.1) на деякому відрізку [a, b].

Припустимо, що рівняння (1.0) можна переписати в виде:

x=((x) (1.3).

Візьмемо довільне значення x0 в галузі визначення функції ((x) і будуватиме послідовність чисел {xn}, певних з допомогою рекуррентной формулы:

xn +1=((xn), n=0, 1, 2, … (2.3).

Послідовність {xn} називається итерационной послідовністю. При її вивченні стають два вопроса:

1) Чи можна процес обчислення чисел xn продовжувати необмежено, т. е. чи буде числа xn належати відтинку [a, b]? 2) Якщо итерационный процес (2.3) нескінченний, те, як поводяться числа xn при n ((.

Дослідження цих питань показує, що з певних обмеженнях на функцію ((x) итерационная послідовність є безкінечною і сходиться до корені рівняння (1.3).

[pic], c=(©.

(3.3).

Але, аби цей дослідження ми мусимо запровадити нове понятие.

Кажуть, що функція f (x) задовольняє на відрізку [a, b] умові Липшица, якщо є така стала (, що з будь-яких x1, x2, що належать відтинку [a, b] має місце неравенство:

| f (x1) — f (x2)| ((|x1 — x2| (4.3).

Значимість (у разі називають постійної Липшица.

Якщо функція f (x), задовольняє на відрізку [a, b] умові Липшица, вона безупинна ньому. Справді, нехай x0 — довільна точка відрізка. Розглянемо прирощення функції f (x) у цій точке:

(f=f (x0+(x) — f (x0).

и оцінимо його з допомогою нерівності (4.3).

|(f | ((|(x|.

Отже, [pic], що означає безперервність функції f (x).

Умова Липшица має простий геометричний сенс. Візьмемо не графіці функції y=f (x) дві довільні точки M1 і M2 з координатами (x1, f (x1)) і (x2, f (x2)). Напишемо рівняння прямий лінії, що проходить через ці точки:

y=f (x1) + k (x-x1).

де k- тангенс кута нахилу прямий у осі Оx й формулой:

[pic].

Якщо функція f (x) задовольняє на відрізку [a, b] умові Липшица, то, при довільному виборі точок M1 і M2 маємо |k|((. Таким чином, з геометричній погляду умова Липшица означає обмеженість тангенса кута нахилу січних, проведених через різноманітні пари точок графіка функції y=f (x).

рис 2.3 рис 3.3 геометрична ілюстрація геометрична ілюстрація умови Липшица. cвязи умови Липшица з пред;

становищем про дифференциру;

емости функции.

Припустимо, що функція f (x) тримає в відрізку [a, b] обмежену похідну: | f ((x)| (m; тоді вона задовольняє умові Липшица із постійною (=m. Для доказательства цього твердження скористаємося формулою кінцевих збільшень Лагранжа:

f (x2) — f (x1) = f ((()(x2-x1) (5.3).

где x1, x2, — довільні точки відрізка [a, b] (, — деяка точка відрізка [x1, x2]. Візьмемо модуль обох частин рівності (4.3) і замінимо в правій частині | f ‘(x)| на m. Через війну получимо нерівність (4.3) з (=m. Рис. 2.3 дає геометричну ілюстрацію встановленого властивості. За формулою Лагранжа (5.3) кожної січною графіка функції y = f (x) можале експортувати відповідність паралельну її дотичну. Тому найбільший тангенс кута нахилу дотичних, і можна оцінити тієї ж константою m: |k| (m.

Познайомившись із умовою Липшица, перейдём до вивчення итерационной послідовності, припускаючи, що рівняння має корінь x=c. Існування цього кореня можна установити з допомогою якісного попереднього дослідження рівняння із застосуванням теореми про існуванні кореня безупинної функции.

Теорема про існування кореня безупинної функции.

Якщо функція f (x) безупинна на відрізку [a, b] та приймає з його кінцях значення різних знаків, то, на цьому відрізку існує, по крайньої мері, один корінь рівняння f (x).

Теорему про збіжності итерационной последовательности.

Хай із — корінь рівняння (2.3) і нехай функція ((x) задовольняє на деякому відрізку [з-(, з+(] ((>0) умові Липшица з постійної (.