Редукційне програмування функцій, зображених степеневими рядами

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

Розглянемо процес конструювання програми методом редукцій згідно з композиційною технологією програмування на прикладі задачі обчислення суми відрізку ряду

(1)

1. Постановка задачі. Задача обчислення (1) очевидно, може розглядатися як задача обчислення значення функції ,,яка задається операцією підсумовування при , тобто , де – довільна, але фіксована функція, залежна від дійсної змінної та змінної , що приймає натуральні значення.

2. Аналіз задачі. Легко зрозуміти, що задача обчислення значення зводиться до задачі обчислення послідовності , що може задаватись рекурентним співвідношенням:

,

де послідовність , у свою чергу, задається рекурентним співвідношенням

.

3. Характеристична властивість задачі. Як випливає з аналізу задачі, функція має таку властивість: їїзначення для будь-яких x та n збігається з членом першої з системи двох послідовностей

,
що визначається системою двох рекурентних співвідношень

(2)
та початковими значеннями . При цьому виконується умова

(3)

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

4. Функціональна структура програми. Аналіз характеристичної властивості функції f(x,n) показує, що функціональною структурою програми може бути (D, W)- іменна функція F = F { Х, N; S } яка іменній множині {(Х,х),(N, n)} зіставляє іменну множину {(S,s)}, де

,
таке, що іменний предикат іменній множині зіставляє значення false, якщо j=n, та значення true для всіх .

Таким чином, функціональна структура програми задається (D,W)-іменною функцією

, де .

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

Для того, щоб розкласти іменну функцію F, яка зіставлена задачі обчислення на первинні або базові функції, використовуючи придатні керуючі структури (композиціі), звернемося до характеристичної властивості функції . Її аналіз показує, що при розкладанні імейної функціі F має використовуватися одна з керуючих структур (композицій) типу циклування, наприклад, while_do.

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

(5)

для та початковими значеннями .

Легко побачити, що при та система послідовностей, яка визначається системою рекурентних співвідношень (5), збігається з системою послідовностей, яка визначається системою рекурентних співвідношень (3) при вказаних початкових значеннях. Отже, при та для будь-яких припустимих значень значення функції збігається зі значенням функції :

= .

Введемо до розгляду (D,W)-іменну функцію , яка іменній множині

(6)

зіставляє іменну множину

, (7)

Тоді, зважаючи на сказане раніше, функцію F можна записати у вигляді:

(8)

Якщо для функції знайдеться редукція , то вона може бути представлена у вигляді: while P do , де Р – придатний предикат.

Нехай – D -іменна -функція, яка іменній множині зіставляє значення .

Покажемо, що (D,W)-іменна функція

є редукцією функції . Для цього пересвідчимось, що виконується визначальна властивість редукції: .

Нехай задана іменна множина (6). Її образ відносно функції є

. Застосувавши до неї отримаємо:

(9)

Але згідно з означенням функції ,

Отже іменна множина (9), на яку функцією перетворюються іменна множина (6), збігається з іменною множиною (7), на яку та ж сама множина (6) перетворюється функцією

Таким чином, функція дійсно є редукцією функції . Тоді останню можна зобразити у вигляді:

while P do ()

Легко зрозуміти, що за Р можна обрати предикат . Це випливає з характеристичної властивості функції .

Беручи до уваги, що функція F, яка нас цікавить, зображувана у вигляді (8), можна зробити останній крок її розкладання, здобувши композиційну структуру цієї функції

while do ( ). (10)

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

Програма 1.

while do .

Безпосередньо з побудови програми випливає її коректність.

Однак, ця програма є неефективною, бо, обчислюючи для будь-якого , вона повторює обчислення . Щоб позбутися необхідності такого повторного обчислення, зобразимо функцію у вигляді . Тоді задача обчислення (1) може розглядатися, як задача обчислення функції , що зображена відрізком степеневого ряду, коефіцієнти якого залежать від номера члена.

Поряд з послідовністю, що визначається рекурентним співвідношенням (5) введемо ще одну послідовність , яка задається рекурентним співвідношенням

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

та початковими значеннями . При цьому виконується умова (4).

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

Програма 2.

Коректність програми випливає з побудови. Проведені розгляди довели справедливість теореми.

Теорема 1.1. Для обчислення функції , де – довільна, але фіксована функція, в елементарній програмній логіці виводиться коректна програма з оракулами (схема програм), яка має вигляд:

.

Це дійсно так, бо, іменні функції, що входять до композиційної структури (10), як у ній самій, так і в процесі її конструювання можуть розглядатись не як конкретні функції, а як довільні, але фіксовані іменні функції. А саме D -іменна -функція, яка іменній множині зіставляє значення , де остання – довільна, але фіксована функція дійсної та натуральної змінних.

Теж саме можна констатувати і відносно програми 2. Тобто, процес композиційного конструювання методом редукцій цієї програми є фактичним доведенням справедливості наступного твердження.

Теорема 1.2. Для обчислення функції , де – довільна, але фіксована функція натуральної змінної , в елементарній програмній логіці виводиться коректна програма з оракулами (схема програм), що має вигляд:

.

Тут – D -іменна -функція, яка іменній множині зіставляє значення .

Теореми 1.1 і 1.2 дозволяють діставати конкретні коректні програми обчислення різних функцій, зображених скінченими відрізками степеневих рядів, шляхом заміни у схемі програм довільних функцій, що входять до неї, відповідними конкретними функціями. Так, наприклад, програма 1 може здобувати ся зі схеми програм теореми 1.1, якщо покласти у ній , а програма 2 – зі схеми програм теореми 1.2 покладанням у ній .

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

2. Коректні схеми програм обчислення функцій, зображених степеневими рядами. Нехай – функція, зображена відрізком степеневого ряду, коефіцієнти якого залежать від номера члена:

(1)

Нехай – D -іменна -функція, яка іменній множині зіставляє значення , а – D -іменний предикат, що іменній множині {(I,i),(N,n)} зіставляє значення . Покажемо, що має місце таке твердження.

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

. (2)

Доведення проведемо.щляхом. безпосередньої побудови методом редукцій виводу в елементарній програмній логіці програми з оракулами (2), користуючись композиційною технологією програмування.

За характеристичну візьмемо таку властивість функції (1): її значення збігається із значенням першої з системи двох послідовностей, що визначається системою двох рекурентних співвідношень першого порядку

(3)

при початкових значеннях , для якого

(4)

Відповідно до композиційної технології програмування з'ясуємо спочатку функціональну структуру програми. Аналіз характеристичної властивості функції (1) показує, що за функціональну структуру програми доцільно обрати (D,W)-іменну функцію F { X,N;S }, яка іменній множині { (X,x),(N,n) } зіставляє іменну множину { (S,s) }, де

таке, що предикат іменній множині {(І,і),(N,n)}зіставляє значення , коли j = n,та значення , коли .

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

Щоб розкласти функцію F, яка задає функціональну структуру програми, за допомогою обраних композицій, проведемо подальший аналіз характеристичної властивості функції (1). Він показує, що при розкладанні функції F має використовуваїtiСЯ композиція типу циклування, наприклад, while-do. Однак застосувати цю композицію одразу на першому кроці розкпадання функції F, як і в попередніх випадках, не можна, бо не вдається природним шляхом знайти редукцію цієї функції. Тому спробуємо, як і раніше, розкласти спочатку функцію F, використовуючи композицію аплікації. З цією метою розглянемо функцію·

, де , такий член послідовності, а , , що предикат приймає значення false, коли та значення true, коли , тобто

. (5)

Ця послідовність є першою в системі двох послідовностей, визначеній системою двох рекурентних співвідношень першого порядку

(6)

для та початковими значеннями .

Легко побачити, що при система послідовностей, яка визначається системою рекурентних співвідношень (4), збігається з системою послідовностей, яка визначається системою рекурентних співвідношень (3) при вказаних початкових значеннях. Отже, при для будь-яких припустимих значень х, n значення функції збігається із значенням функції .

Введемо до розгляду (D,W)-іменну функцію , яка іменній множині

(7)

зіставляє іменну множину

, (8)

Тоді, зважаючи на сказане раніше, функцію F можна записати у вигляді:

(9)

Якщо для функції знайдеться редукція , то вона може бути представлена у вигляді: while P do , де Р – придатний предикат.

Нехай – (D,W) -іменна функція: . Покажемо, що вона є редукцією функції . Для цього пересвідчимось, що для цих функцій виконується основна редукційна властивість.

Нехай задана іменна множина (7). Її образ відносно функції є

. Застосувавши до неї отримаємо:

(10)

Але згідно з означенням функції ,

Отже іменна множина (10), на яку функцією перетворюються іменна множина (7), збігається з іменною множиною (8), на яку та ж сама множина (7) перетворюється функцією

Таким чином, функція дійсно є редукцією функції . Тоді останню можна зобразити у вигляді:

while P do ()

Легко зрозуміти, що за Р можна обрати предикат . Це випливає з характеристичної властивості функції .

Беручи до уваги, що функція F, яка нас цікавить, зображувана у вигляді (9), можна зробити останній крок її розкладання, здобувши композиційну структуру цієї функції

while do ( ).

Ця композиційна структура, очевидно, являє собою програму з оракулами (2), що обчислює функцію (1). Безпосередньо з побудови випливає її коректність. Теорема доведена.

Теорема 2.1 дозволяє діставати коректні програми обчислення різних функцій, зображених відрізками степеневих рядів, шляхом заміни в схемі програм довільних функцій, що входять до неї, відповідними конкретними функціями. Однак ці програми передбачають незалежне обчислення кожного члена ряду, що призводить до досить громіздких обчислень. Справді, проаналізувавши схему програм (2) з погляду її ефективності, неважко зрозуміти, що вона є неефективною, тому що при незалежному обчисленні членів суми, яка задає функцію (1), буде виконуватись багато однакових обчислень. Дійсно, для будь-якого значення і>2 при обчисленні мають обчислюватися , які вже обчислювалися. Щоб позбавитися необхідності такого багаторазового обчислення, поряд із послідовностями, які визначаються системою рекурентних співвідношень (3) та вказаними початковими значеннями, введемо до розгляду ще одну послідовність . Візьмемо за характеристичну таку властивість функції (1): ії значення збігається зі значенням такого члена першої з системи трьох послідовностей, що визначається системою трьох рекурентних співвідношень першого порядку

(11)

при та початкових значеннях , для якого виконується (4).

Справедливе таке твердження.

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

while do ( ).

Доведення цієї теореми проведемо с за аналогією до доведення теореми 2.1.Аналізуючи останню характеристичну властивість функції (1), можна дійти висновку, що за функціональну структуру програми може бути обрана та ж сама функція F { X,N;S }, що і в доведенні теореми 2.1. Що ж до композиційної структури програми, то з метою розкладання функції F на більш прості функції за допомогою композицій структурного програмування розглянемо функцію , де , такий член послідовності, а , , що предикат приймає значення false, коли та значення true, коли , тобто

.

Ця послідовність є першою в системі трьох послідовностей, визначеній системою трьох рекурентних співвідношень першого порядку

(12)

для та початковими значеннями .

Легко побачити, що при система послідовностей, яка визначається системою рекурентних співвідношень (12), збігається з системою послідовностей, яка визначається системою рекурентних співвідношень (11) при вказаних початкових значеннях. Отже, при для будь-яких припустимих значень х, n значення функції збігається із значенням функції .

Введемо до розгляду (D,W)-іменну функцію , яка іменній множині

(13)

зіставляє іменну множину

, (14)

Тоді, зважаючи на сказане раніше, функцію F можна записати у вигляді:

(15)

Якщо для функції знайдеться редукція , то вона може бути представлена у вигляді: while P do , де Р – придатний предикат.

Нехай – (D,W) -іменна функція: . Покажемо, що вона є редукцією функції . Для цього пересвідчимось, що для цих функцій виконується основна редукційна властивість.

Нехай задана іменна множина (13). Її образ відносно функції є

. Застосувавши до неї отримаємо:

(16)

Але згідно з означенням функції ,

Отже іменна множина (16), на яку функцією перетворюються іменна множина (13), збігається з іменною множиною (14), на яку та ж сама множина (13) перетворюється функцією

Таким чином, функція дійсно є редукцією функції . Тоді останню можна зобразити у вигляді:

while P do ()

Легко зрозуміти, що за Р можна обрати предикат . Таким чином,

while do ()

Беручи до уваги, що функція F, яка нас цікавить, зображувана у вигляді (15), можна зробити останній крок її розкладання, здобувши композиційну структуру цієї функції

while do ( ).

Ця композиційна структура, очевидно, являє собою програму з оракулами (2), що обчислює функцію (1). Причому, також очевидно, що дана композиційна структура збігається з програмою, наведеною в теоремі 1.2. Безпосередньо з побудови випливає її коректність. Теорема доведена.

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

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

(17)

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

(18)

Коректність здобутих у такий спосіб програм обгрунотвується шляхом конструювання відповідних програм з оракулами (схем програм).

Нехай R { Х,І } – D -іменна -функція, яка іменній множині зіставляє значення . Покажемо, що справедливе таке твердження.

Теорема 2.3. Якщо обчислення функції (1) зводиться до обчислення суми (17), члени якої послідовно обчислюються за рекурентними співвідношеннями (18), то схема програм (програма з оракулами) такого обчислення, зображувана у вигляді

І:= 0; U:=A { 0 }; S:= A { 0 };

while do ( )

виводиться в елементарній програмній логіці і є коректною.

Для доведення теореми за характеристичну властивість функції (1), яка задовольняє умові теореми, приймемо те, що будь-яке значення цієї функції збігається зі значенням такого члена першої з системи трьох послідовностей, визначеної системою трьох рекурентних співвідношень першого порядку

(19)

та початковими значеннями , для якого справедлива умова (4).

Функціональна структура, як і в доведеннях теорем 2.1 і 2.2, може виражатися функцією F { X,N;S }. З метою ж одержання композиційної структури програми введемо до розгляду функцію , де , такий член послідовності, а , , що предикат приймає значення false, коли та значення true, коли , тобто

.

Ця послідовність є першою в системі трьох послідовностей, визначеній системою трьох рекурентних співвідношень першого порядку

(20)

для та початковими значеннями .

Легко побачити, що при система послідовностей, яка визначається системами рекурентних співвідношень (19) та (20), звідки випливає рівність .

Введемо до розгляду (D,W)-іменну функцію , яка іменній множині

(21)

зіставляє іменну множину

, (22)

Тоді, зважаючи на сказане раніше, функцію F можна записати у вигляді:

(23)

Якщо для функції знайдеться редукція , то вона може бути представлена у вигляді: while P do , де Р – придатний предикат. Доведемо, що (D,W) -іменна функція: є редукцією функції . Для цього пересвідчимось, що для цих функцій виконується основна редукційна властивість.

Нехай задана іменна множина (21).. Її образ відносно функції є . Застосувавши до неї отримаємо:

.

Але згідно з означенням функції ,

Таким чином, функція дійсно є редукцією функції . Тоді, враховуючи (23), функцію можна представити так:

while do ()

Цим теорема 2.3 доведена.

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

Зазначимо, що теореми, аналогічні теоремам 2.1-2.3, можуть доводитися для таких випадків відрізків степеневих рядів, коли номер останнього члена суми не задається явно, а визначається вимогою, щоб останній член не перевищував за абсолютною величиною задане число .

Слід також зауважити, що всі наведені в роботі теореми залишаються вірними для функції та – функція, аргумент і значення якої – натуральні числа.

3. Коректні програми і схеми програм обчислення функцій, зображених степеневими рядами.

Цей розділ присвячено питанню редукційного програмування коректних програм і схем програм обчислення функцій, зображених степеневими рядами. Він є логічним продовженням попередніх розділів, де це питання вже розглядалося. Так, у розділі 1 показується, як залежно від обраної тієї чи іншої характеристичної властивості конкретної функції з вказаного класу можна здійснити редукційне конструювання різних, перш за все за своєю ефективністю, коректних програм її обчислення. При цьому увага зосереджується на самому процесі редукційного програмування, бо саме його безпосереднім наслідком є коректність здобутої в результаті програми. У розділі 2 в елементарній програмній логіці виводяться коректні програми з оракулами (схеми програм), що дозволяють підставленням у них замість довільних функцій відповідних конкретних функцій діставати конкретні коректні програми обчислення різних функцій, зображених степеневими рядами. Тут зупинимося на питаннях, пов'язаних із можливістю встановлення коректності окремих програм обчислення функцій, зображених степеневими рядами, в один з двох способів: або потрібна конкретна програма дістається відповідною підстановкою з відповідної коректної схеми програм, або ж здійснюється її безпосереднє редукційне конструювання, яке забезпечує її коректність. Зокрема, повернемося до питання, яким закінчується розділ 1: чи варто конструювати методом редукцій окремі коректні програми, якщо можна спочатку сконструювати коректні схеми програм для тих чи інших класів задач, а вже потім діставати з цих схем відповідні необхідні конкретні коректні програми, як це зроблено у наведених прикладах? З цією метою розглянемо ще два приклади редукційного програмування функцій, зображених степеневими рядами.

Приклад 3.1. Написати програму обчислення суми степеневого ряду для

(1)

Якщо номер останнього члена ряду, що залишається, задається явно, то задача обчислення (1), очевидно, може розглядатися як задача обчислення значення функції

(2)

Як випливає з аналізу функції , вона має три наведених нижче властивості.

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

(3)

та початковими значеннями . При цьому виконується умова

(4)

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

т та початковими значеннями . При цьому виконується умова (4).

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

та початковими значеннями , для якого справедлива умова (4).

Будь-яку з цих властивостей функції можна обрати за характеристичну для розробки програми обчислення її значень.

Аналіз наведених властивостей 1-3 показує, що незалежно від того, яка з них обирається за характеристичну властивість функції , функціональною структурою програми обчислення може бути (D,W)-іменна функція F = F { X,N;S }, яка іменній множині {(X,x),(N,n)} зіставляє іменну множину {(S,s)}, де

,

таке, що іменний предикат іменній множині зіставляє значення , якщо , та значення для всіх .

Таким чином, функціональна структура програми задається (D,W)-іменною функцією , де .

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