Загальні питання наближення функцій (реферат)

Реферат на тему:

Загальні питання наближення функцій

Теорія наближень є фундаментом багатьох чисельних методів. Ефективність чисельного алгоритму може у великій мірі залежати від способу наближення шуканого розв’язку. Теорія наближень оформилась у змістовну теорію в ХХ сторріччі, хоча перші результати її були одержані П. Л. Чебишовим в 1853 і 1857 роках, а знамениту теорему Вейєрштрасса доведено в 1885 році.

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

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

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

Нехай u — заданий елемент нормованого лінійного простору U, а V підпростір в U, що складається з елементів вигляду.

v= $$\underset{i=1}{\overset{n}{}}$$ i vi, (1).

де vi — фіксовані лінійно незалежні елементи з V, $$$$ i — числа.

В залежності від того, належить u простору V, чи ні, виникає дві задачі:

1. uV. Треба визначити коефіцієнти i розкладу u за функціями vi: u= $$\underset{i=1}{\overset{n}{}}$$ i vi .

2. uV. Для u відшукується наближення вигляду (1), коефіцієнти якого визначаються з умови мінімізації відстані $$=u-v\text{.}$$.

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

До 1-го і 2-го випадків відносяться інтерполяція та апроксимація в різних функціональних просторах.

Припустимо, що в точках xj (j= $$\stackrel{}{\mathrm{0,}m}$$) відомі значення функції uj. Треба відшукати функцію v вигляду (1), яка в даних точках xj найменшим чином відхиляється від значень uj, тобто величини.

$$d_j$$ = uj — $$\underset{i=1}{\overset{n}{}}$$ i vi, j= $$\stackrel{}{\mathrm{1,}m}$$.

повинні бути мінімальними. Задача полягає у визначенні $$$$ i.

1. n=m. Якщо det (vk (xj)) $$\mathrm{^1}$$ 0, то можна одержати $$d_j$$ =0, визначивши з цієї умови $${}_i$$ шляхом розв’язування системи лінійних алгебраїчних рівнянь (ЛАР). Кажуть, що у цьому випадку вираз v= $$\underset{i=1}{\overset{n}{}}$$ i vi інтерполює функцію u .

Для того, щоб det (vk (xj)) не дорівнював нулю для обраної системи функцій vk (x) і будь-якого набору вузлів xj ($$x_i\mathrm{^1}{x}_j$$ при $$i\mathrm{^1}j$$) необхідно і достатньо, щоб система функцій $$\left\{v_k(x)\right\}$$ була системою Чебишова.

Означення. Система функцій v1(x), v2(x),…, vn (x) називається системою Чебишова на [а, b], якщо будь-який узагальнений поліном $$\underset{i=1}{\overset{n}{}}$$ i vi (x), у якого хоча б один з коефіцієнтів відмінний від нуля, має на [a, b] не більше n нулів.

2. n<m В цьому випадку ми одержуємо задачу пошуку елемента найкращого наближення:

u (x) v (x) = $$\underset{i=1}{\overset{n}{}}$$ i vi (x).

Функції vk задано, а сталі визначаються з умови мінімальності відстані $$u-v$$ .

Міра відстані визначається простором, в якому розглядається наближення.

Числова множина (u, v)= $$u-v$$. при фіксованій функції u обмежена знизу числом 0, тому існує (u)= $$\underset{\mathit{v^IV}}{\text{inf}}\left(u,v\right)$$ .

Елемент v0, для якого має місце рівність (u)= $$u-v_0$$ називається елементом найкращого наближення для u в просторі V або проєкцією u на V.

Теорема. Для будь-якого елементу u лінійного нормованого простору U, в V існує елемент найкращого наближення. Якщо простір U, строго нормований, то цей елемент єдиний.

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

$$u-v$$ = ($$\underset{B}{}{|u-v|}^2$$ dx)½.

(B — область, в якій задано u та v), а також в просторі C (рівномірне або чебишовське наближення), де.

$$u-v$$ = $$\underset{B}{\text{sup}}|u-v|$$ .

Замість лінійної апроксимації (1) можна використовувати також раціональну апроксимацію, де.

u (x) v (x)= $$(\underset{}{\overset{s}{}}{}_i{v}_i(x))/(\underset{}{\overset{t}{}}{}_i{v}_i(x))$$ .

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

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

F (x, $$\stackrel{}{}$$)=F (x, $$$$ 1, $$$$ 2,…, $$$$ n),.

де F — задана функція, залежна від параметрів $$$$ j, при цьому $$$$ j визначаються з умови.

$$u(x)-F(x,\stackrel{}{})$$ =min.

Отже, приступаючи до задачі наближення функції, треба знайти відповіді на такі питання:

1. Якою наявною інформацією ми володіємо?

2. Який клас наближуючих функцій використати?

3. Якою мірою оцінити близькість функцій u та v ?

4. Яка точність потрібна ?

Обговоримо коротко ці питання.

1. На практиці наявна інформація про функцію часто задається зовнішніми обставинами, наприклад, коли в незалежні від дослідника моменти часу t1, t2, …, tm спостерігаються значення функції u (t), і потрібно відновити її значення при інших t.

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

2. Як випливає з розглянутої постановки задачі, найчастіше наближуючими функціями обирають поліноми (алгебраїчні, тригонометричні, експоненційні), рідше їх відношення. Вигляд наближуючої функції істотно залежить від мети наближень. Припустимо, що деяку функцію можна з потрібною точністю наблизити або степеневим поліномом шостого степеня або тригонометричним виразом. Перша форма зручніша для багатократних обчислень на ЕОМ, а друга — для реалізації на моделюючих пристроях або для теоретичних досліджень.

3. Вибір близькості функцій u i v в першу чергу визначається фізичним змістом задачі і лише потім — математичними міркуваннями.

4. Кількісна оцінка точності одержаного наближення до точного розв’язку часто є непростою задачею. Міри точності відповіді залежать від конкретних ситуацій:

— Чи існує не груба і досить проста для практичного використання теоретична оцінка точності ?

— Чи повинен алгоритм давати розв’язок модельної задачі з необхідною кількістю точних знаків ?

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

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

Досить поширеним на практиці є відоме з курсу аналізу наближення функціІ поліномом Тейлора n-го степеня, яке для u (x) Cn+1[a, b] має вигляд:

Pn (x)= $$\underset{i=0}{\overset{n}{}}{u}^{(i)}(x_0)(x-x_0{)}^i/i!$$ .

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

u (x) — Pn (x)= $$u^{(n+1)}(x^{})(x-x_0{)}^{n+1}/(n+1)!$$, (2).

де x [a, b], x* лежить строго між х і х0 .

З припущення, що u (n+1) C[a, b], випливає, що $$M_{n+1}=\underset{\left[a,b\right]}{\text{max}}|(n+1)(x)|\text{<yen}$$. Тоді з (2) маємо.

$$|u(x)-P_n(x)|<=M^{n+1}{|x-x_0|}^{n+1}/(n+1)!$$ ,.

$$\underset{\left[a,b\right]}{\text{max}}|u(x)-P_n(x)|<=M_{n+1}{l}^{n+1}/(n+1)!$$, (3).

де l = max (x-a, b-x).

Неважко бачити, що похибка наближення функції поліномом Тейлора різко зростає біля кінців відрізку [a, b]. Принаймі це так, якщо u (n+1)(x)=const $$\mathrm{^1}$$ 0, тобто u (x) — поліном степеня n+1. Тоді u (n+)(x) =Mn+1 і (3) перетворюється в рівність. Крім розкладу функції u (x) за системою функцій 1, (x-x), (x-x)2, …, функціями v (x) можна обирати спеціальні функції, такі як поліноми Чебишова, Лежандра, Лагерра, функції Бесселя та інші.

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

fk+1(x) = A (k, x) fk (x) + B (k) fk-1 (x), k=1,2,.,.

де коефіцієнти А, В заздалегідь визначені.

Якщо спеціальні функції - поліноми, то, знаючи f0 i f1, поліноми більш високих степенів обчислити не важче, ніж складові степеневого ряду. Так, наприклад, система поліномів Лежандра, ортогональна на [-1,1], визначається співвідношенням.

$$P_{k+1}(x)=\frac{2k+1}{k+1}{\text{xP}}_k(x)-\frac{k}{k+1}{P}_{k-1}(x),$$ $$P_0(x)=1-$$ $$P_1(x)=x\text{.}$$.

ЗАУВАЖЕННЯ.

1. Наближуючи функції узагальненими поліномами, часто цими поліномами обирають степеневі поліноми 1, x, x2, …. Система {xi} є повною в C [0,1] і не лише повною, але й переповненою. Так, з усіх цих функцій можна залишити лише ті, для яких показник — просте число або нуль, і одержана система залишиться повною. Використання переповнених систем в чисельному аналізі небажане, а на думку багатьох авторитетів у цій галузі і неприпустиме. Тому від системи {xi} необхідно переходити до систем ортогональних поліномів.

2. Задача обчислення значення полінома Pn (x)= $${}_0{x}^n+{}_1{x}^{n-1}+\text{.}\text{.}\text{.}+{}_n$$ для конкретного значення х реалізується схемою Горнера. Записуючи Pn (x) у вигляді Pn (x)= $$(\text{.}\text{.}({}_{0}x+{}_1)x+{}_2)x+\text{.}\text{.}\text{.})x+{}_n$$ бачимо, що обчислення можна вести за формулою Aj+1=Ajx+j, j=0,1,…nA0=0. В підсумку одержуємо An+1=Pn (x).

Схема Горнера є оптимальною в тому відношенні, що потребує мінімально можливого числа множень.

Схему Горнера можна застосовувати і для обчислення значень сум вигляду:

Sn (x)= $$\underset{k=0}{\overset{n}{}}{a}_k{f}_k(x)$$ ,.

де функції {fk (x)} і f-1(x) задовольняють тричленному рекурентному співідношенню.

fk+1(x)+ak (x)fk (x)+bk (x)fk-1(x)=0, k=0,1,., n.

Схема обчислення значення Sn (x) є безпосереднім узагальненням схеми Горнера: будуємо послідовність.

Aj= $${}_j$$ — aj Aj+1 — bj Aj+2, j=n, n-1,., 0: An+1=An+2=0.

і одержуємо Sn (x)=A0 f0(x).

ВПРАВИ.

1. Довести, що в лінійному нормованому просторі:

а) множина елементів найкращого наближення опукла;

б) якщо простір строго нормований, то елемент найкращого наближення єдиний.

2. Нехай $$C_0$$ — простір послідовностей дійсних чисел, які прямують до нуля- $$\mathit{x^I}$$ $$C_0$$, якщо $$x=\left(x_1,\text{.}\text{.}\text{.},x_n\right),$$ де $$x_n->0$$ при $$n->\mathrm{yen},\begin{array}{cc}& x\end{array}=\underset{n}{\text{max}}|x_n|$$. Побудувати в $$C_0$$ замкнений підпростір $$L$$, що має таку властивість: для будь-якого $$\mathit{x"\; IL}$$ в підпросторі $$L$$ не існує елементу найкращого наближення.

3. Нехай $$\left\{u_0,u_1,\text{.}\text{.}\text{.},u_n\right\}$$ — система Чебишова і $$$$ $$A={\left(a_{\text{ij}}\right)}_{i,j=0}^n$$ — невироджене лінійне перетворення. Довести, що система функцій $$\left\{u_0,u_1,\text{.}\text{.}\text{.},u_n\right\}$$, де $$v_i\left(x\right)=\underset{j=0}{\overset{n}{}}{a}_{\text{ij}}{u}_j,\begin{array}{cc}& i=\stackrel{}{\mathrm{0,}n}\end{array}$$ також є чебишовською.

4. Чи є система функцій $$\mathrm{1,}x,x^2,\text{.}\text{.}\text{.},x^n$$ чебишовською на $$\left[a,b\right]$$ ?

5. Довести, що простір $$L_2\left[\mathrm{0,1}\right]$$ є нормованим.

6. Довести, що простір $$L_1\left[\mathrm{0,1}\right]$$ не є строго нормованим.

1. 7. Чи є простір $$L_2\left[\mathrm{0,1}\right]$$ строго нормованим?

2. 8. Довести, що сукупність функцій $$1/P\left(x\right),x/P\left(x\right),\text{.}\text{.}\text{.},x^n/P\left(x\right),$$ де $$P\left(x\right)$$ — поліном, утворює систему Чебишова на будь-якому відрізку, на якому $$P\left(x\right)$$ не має нулів. $$$$.

9. Довести, що функції $$\mathrm{1,1}/\left(a_1+x\right),\text{.}\text{.}\text{.}\mathrm{,\; 1}/\left(a_n+x\right)$$ утворюють систему Чебишова при $$x>\mathrm{0,}$$ якщо $$a_k>0\begin{array}{cc}& \left(k=\mathrm{0,1,}\text{.}\text{.}\text{.}\right)\end{array}\text{.}$$.

10. Чи є система $$j_0\left(x\right)=\mathrm{1,}{j}_1\left(x\right)=\text{cos}x$$ системою Чебишова ?

11. Побудувати алгоритм реалізації схеми Горнера для обчислення значення $$P_n\left(x\right)$$ на $$r$$ паралельно працюючих процесорах.

12. Нехай коефіцієнти полінома $$P_n\left(x\right)={}_0{x}^n+{}_1{x}^{n-1}+\text{.}\text{.}\text{.}+{}_n$$ дійсні, а $$x=u+\text{iv}$$ — комплексне. Побудувати схему обчислення $$P_n\left(x\right)$$, що потребує $$2n+2$$ множення і $$$$ $$2n+2$$ додавання.