Обчислення значень полінома. Схема Горнера

ОБЧИСЛЕННЯ ЗНАЧЕНЬ ФУНКЦІЙ

При обчисленні за допомогою комп'ютерів значень функцій, заданих формулами, далеко не байдуже, у якому виді записана відповідна формула. Математично еквівалентні вирази часто виявляються нерівноцінними з погляду наближених обчислень. Тому виникає практично важлива задача про знаходження для елементарних функцій найбільш зручних аналітичних виразів. Обчислення значень функцій звичайно зводиться до послідовності елементарних арифметичних дій. З огляду на обмеженість об'єму пам'яті комп'ютера, бажано ці операції розбивати на повторювані цикли. Нижче ми розглянемо деякі типові прийоми обчислень.

Обчислення значень полінома. Схема Горнера

Нехай даний поліном -й степеня

(1)

с дійсними коефіцієнтами . Нехай потрібно знайти значення цього полінома при (грецька буква «ксі»):

. (2)

Обчислення числа зручніше за все робити в такий спосіб. Представимо формулу (2) у вигляді:

.

Звідси, послідовно обчислюючи числа

знаходимо .

Неважко довести (спробуйте це зробити самостійно), що числа є коефіцієнтами полінома , отриманого як частку при діленні даного полінома на двочлен .

Таким чином, формули (3) дозволяють, не роблячи ділення, визначати коефіцієнти частки ,а також остачу . Практично обчислення здійснюються за наступною схемою, називаною схемою Горнера:

Приклад 1. Обчислити значення полінома

при .

Розв’язок. Складемо схему Горнера:

Зауваження. Користуючись схемою Горнера, можна одержати границі дійсних коренів даного полінома .

Припустимо, що при всі коефіцієнти в схемі Горнера невід’ємні, причому перший коефіцієнт додатний, тобто

. (6)

Тоді можна стверджувати, що всі дійсні корені полінома розташовані не правіше , тобто (мал. 1).

Рис. 1.

Справді, тому що

,

то при кожному в силу умови (6) будемо мати ,тобто будь-яке число, більше , завідомо не є коренем полінома . Таким чином, маємо верхню оцінку для дійсних коренів полінома.

Для одержання нижньої оцінки коренів складемо поліном

.

Для цього нового полінома знаходимо таке число , щоб всі коефіцієнти у відповідній схемі Горнера були невід’ємні, за винятком першого, котрий, очевидно, буде позитивним. Тоді відповідно до попередніх міркувань для дійсних коренів полінома , очевидно, рівних ,маємо нерівність .

Отже, . Таким чином, ми одержали нижню границю дійсних коренів полінома . Звідси випливає, що всі дійсні корені полінома розташовані на відрізку .

Приклад 2. Знайти границі дійсних коренів полінома

.

Розв’язок. Підрахуємо значення полінома , наприклад, при . Користуючись схемою Горнера, одержимо:

Тому що всі коефіцієнти , то дійсні корені полінома (якщо вони існують) задовольняють нерівності . Верхня границя дійсних коренів знайдена. Перейдемо до оцінки нижньої границі. Складемо новий поліном:

.

Підраховуючи значення полінома ,наприклад, при , маємо:

Всі коефіцієнти , виходить, .

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