Альгарытмы

Некаторыя альгарытмы

Мэтад Гауса дзеля рашэньня сыстэмаў лінейных роўнасьцяў

Даволі лёгка рашаць такія сыстэмы мэтадамі матрычнай альгебры (праз дэтэрмінанты і г.д.) але звычайна лягчэй выкарыстоўваць мэтад Гауса. Ідэя ў тым, каб пазбаўляцца ад зменных, дамнажаючы кожную роўнасьць на пэўны каэфіцыент і потым адымаючы гэтую роўнасьць ад наступнай роўнасьці ў сыстэме так, каб каэфіцыент каля жаданай зьменнай стаў нулём. Пасьля ўсіх гэтых зьдзекаў зыходная сыстэма выглядае так:

a*x + b*y + c*z + d = 0
e*x + f*y + g = 0
i*x + j = 0

Рашаць такую сыстэму ўжо значна прасьцей, чым зыходную. Прыклад праграмы - тутака Gauss.pas.

Зваротная Польская Занатоўка

Найпрасьцейшая сыстэма запісу формулаў для кампутара - Зваротная Польская Занатоўка. Напрыклад, выраз "(a + b)*(c - d)/sin(e)" запісваецца як "a b + c d - * e sin /". Вам ня патрэбныя скобкі ў гэтай сыстэме ды любая формула можа быць проста вылічана зь выкарыстаньнем стэка. Калі сустракаеце зьменную, засуньце яе ў стэк, а калі сустрэнеце функцыю альбо апэратар, высуньце некалькі зьменных, ажыцьцявіце апэрацыю ды засуньце вынік зваротна ў стэк. Напрыканцы, высуньце канчатковы вынік з стэка (калі выраз быў запісаны правільна, гэта будзе адзіны элемент стэка).

Пераклад традыцыйных формулаў у ЗПЗ - трохі больш складаная аперацыя. Яна таксама ажыцьцяўляецца зь выкарыстаньнем стэку, але зараз гэта стэк матэматычных аперацыяў. Прыярытэт аперацыяў такі:

Функцыі (sin, cos) ды скобкі
Памнажэньне ды дзяленьне
Даданьне ды адыманьне

Сэнс мэтада такі:

Калі сустракаеце зьменную, тады запісвайце яе адразу ў ЗПЗ-формулу
Калі сустракаеце аперацыю, тады высуньце з стэка ўсе аперацыі з вышэйшым прыярытэтам, потым засуньце яе ў стэк
Калі сустракаеце пачынаючую скобку, засуньце яе ў стэк
Калі сустракаеце зачыняючую скобку, высуньце са стэка ўсё да пачынаючай скобкі. Ўласна скобкі ў ЗПЗ-формулу запісваць не трэба
Калі ўся зыходная формула ўжо прачытаная, высуньце ўсё, што засталося ў стэку

Вось модуль для Delphi з такім мэтадам Calculator.pas.

Прыблізныя мэтады

Амаль усе прыблізныя мэтады заснаваныя на раскладаньні Тэйлара:

Калі-некалі гэта працуе толькі для абмежаваных d, а таксама найлепшая дакладнасьць ня павялічваецца зь павелічэньнем колькасьці ітэрацыяў. Каб знайсьці прыблізны лік зь патрабуемай дакладнасьцю, параўноўвайце кожнае наступнае даданае зь цякучым вынікам.

Прыклад праграмы - тутака Tailorrw.pas

А вось добры мэтад, каб рашаць любыя сыстэмы роўнасьцяў. Няхай сыстэма запісваецца ў такім выглядзе: f_i(x₁,x₂,...,x_n)=0, i=1..n. Выкарыстоўваючы лінейную апраксымацыю, будзем шукаць наступную k-ю апракцымацыю рашаючы такую сыстэму лінейных роўнасьцяў адносна x_j^k:

У выпадку аднамернай функцыі гэтыя апэрацыі выглядаюць так:

Некаторыя карысныя роўнасьці

- 2D-хвалі на вадкіх паверхнях
- Роўнасьць дзеля салітонаў
- Роўнасьць дзеля салітонаў у плазме, на паверхні вадкасьці
- Нястацыянарнае разьмеркаваньне тэмпературы
- Роўнасьць Шродзінгера
- Роўнасьць Ван-Дэр-Поля дзеля электрычнага радыёгенератара

Мадэляваньне галаграфіі ды інтэрфэрэнцыі

Мадэляваньне галаграфіі як прыватнага выпадку інтэрфэрэнцыі ды ўласна інтэрфэрэнцыі патрабуе складаньня вялікай колькасьці палёў з аднолькавым перыядам, але рознымі фазамі ды амплітудамі: . Выніковая інтэнсіўнасьць:
Прыклад праграмы - тутака Golography.zip

Мадэляваньне руху зараджаных часьцінак

Гэта толькі рашэньне Н’ьтанаўскіх альбо Эйнштэйнаўскіх роўнасьцяў руху ў сумарным полі ўсіх часьцінак. Прыклад праграмы - тутака Motion.zip

Зьцісканьне графікі
зь выкарыстаньнем 2D - спэктральнага аналізу

Як і ў выпадку Фур’е раскладаньня па адной зьменнай, ў 2D-выпадку Фур’е раскладаньне выглядае так:

Заўважце, што зараз мы працуем зь хвалевымі вектарамі k і фаза вылічаецца як f=k*r, дзе r = {x, y}. Такім чынам, зыходны малюнак зьціскаецца ў пэўную колькасьць хвалевых вектараў. Заўважце: якасьць сапраўды адметная ;)), але ж гэта толькі эксперыментальная праграма. Як рабіць гэта на Delphi? Глядзі Compression.pas.

Гульня "Жыцьце"

Жыцьце - гульня:
сюжэт ня вельмі, затое класная графіка

Ў гэтай вэрсіі папулярнай гульні ёсьць "Мірныя" (дадатныя лікі) ды "Чужынцы" (адмоўныя лікі), таксама магчыма "карміць" іх, заўважце "Мірныя" ды "Чужынцы" ядуць "дадатную" ды "адмоўную" ежу. Выкарыстоўвайце клявішы "up","down","left","right" каб рухаць курсор, клявішы "+/-" (без Шыфта) каб пакінуць на месцы курсора дадатных альбо адмоўных "істотаў", клявішы "0" ды "9" каб пакінуць на месцы курсора дадатную альбо адмоўную ежу. Пасьля націсьніце ESC каб пачаць гульню.
Яшчэ дзве цікавыя мадыфікацыі - Жыцьце ў трох вымярэньнях і Жыцьце на паверхні тора, што ёсьць тапалагічна абмежаванай, але кантынуальна бясконцай прасторай.
Прыклад праграмы Life.pas
Наступныя праграмы - для Delphi і OpenGL пад Delphi: Life3D.zip LifeTor.zip
Гатовыя праграмы: LifeTor.exe

Метад найменьшых квадратаў

Метад найменьшых квадратаў - просты ды хуткі метад для атрыманьня невядомых парамэтраў у функцыянальных залежнасьцёх ды для ацэнкі эксперыментальнай памылкі вымярэньняў. Няхай чакаемай залежнасьцю ёсьць:
y = f(x), і мы атрымалі мноства вымераных значэньняў зьменных(x_i, f(x_i)). Канчатковая памылка можа быць ацэненай сумай квадратаў усіх адхіленньняў ад тэарэтычнай залежнасьці: (x_i - x₀)², дзе х₀ - сярэдняя велічыня х. Дзеля дасягненьня найлепшых вынікаў гэтая памылка маецца быць мінімальнай. Таму возьмем першую вытворную ад гэтай сумы па ўсіх парамэтрах і зраўняем яе зь нулём - такім чынам атрымаем сістэму роўнасьцяў, зь якой можна знайсьці ўсе патрабуемыя парамэтры. У выпадку лінейнай залежнасьці (а амаль усе залежнасьці могуць быць зведзеныя да лінейных) найбольш імавернымі значэньнямі парамэтраў ёсьць:
y = a*x + b


Калі b - нуль, тады формулы становяцца значна прасьцей:
y = a*x

Выкарыстоўваючы гэткі мэтад, можна знаходзіць парамэтры адвольных функцыянальных залежнасьцяў. Напрыклад, наступны мэтад быў выкарыстаны падчас дасьледваньняў ўласьцівасьцяў фрактальных структураў (гл. Тэорыя працяканьня). Вынікі сэрыі эксперымэнтаў - булевыя велічыні Res_i, што залежаць ад лічбавага парамэтра q_i. Патрабуецца знайсьці такое крытычнае q_cr, што для большасьці q_i<q_cr вынік - true (пазытыўны), а для большасьці q_i>q_cr вынік - false (адмоўны). Каб знайсьці гэты парамэтр, я разгледзіў функцыю памылак R_i(Res_i,q_i,q_cr):
R_i(Res_i,q_i,q_cr) = 1, калі q_i<q_cr ды Res_i=False альбо q_i>q_cr ды Res_i=True
R_i(Res_i,q_i,q_cr) = 0 для ўсіх астатніх выпадкаў.
Для нейкага q_cr сумарная памылка ёсьць:
E =SR_i(Res_i,q_i,q_cr)(q_i-q_cr)²
Каб мінімізаваць яе, будзем разглядаць R_i(Res_i,q_i,q_cr) як канстанты і выкарыстаем пэўнае стартавае значэньне q_cr. Бяручы вытворную ад функцыі сумарнай памылкі E па q_cr, знаходзім першае прыблізнае значэньне q_cr. Гэта рэкурэнтны працэс, і j-е прыблізнае значэньне для q_cr ёсьць:
q_cr j =SR_i(Res_i,q_i,q_cr j-1)*q_i / SR_i(Res_i,q_i,q_cr j-1)
Пасьля некалькіх ітэрацыяў нявызначанасьць "0 / 0" можа выклікаць памылку. Тады ітэрацыі трэба спыніць, таму што правільнае значэньне ўжо знойдзена.

Тэксты праграмаў для выпадкаў агульнай і прама прапарцыянальнай залежнасьцяў LSM.pas LSM1.pas
Гатовыя праграмы LSM.exe LSM1.exe

Вылічэньне нявідавочных функцыяў, зададзеных вызначанымі інтэграламі

Функцыі могуць быць заданыя нявідавочна вызначаным інтэгралам:
g(a) = т^b1_b2 f(x,a)dx
Тут як b1, так і b2 могуць імкнуцца да бясконцасьці, альбо сама функцыя f(x,a) можа імкнуцца да бясконцасьці ў якіхсьці кропках паміж b1 і b2. Прыблізнае вылічэньне вызначанага інтэграла - не найхутчэйшы мэтад вылічэньня нявідавочнай функцыі. Больш за тое, гэты мэтад можа быць ня вельмі карысным, калі межы інтэграваньня b1 ды b2 імкнуцца да бясконцасьці. Што ж рабіць? Выкарыстаньне раскладаньня ў рад ды аналітычнае інтэграваньне ўсіх дадатнікаў у радзе - даволі зручны мэтад. Найпростымі радамі ёсьць рады Тэйлара альбо Фур'е. Аднак раду Тэйлара ўласьцівы адзін недахоп: ён няпрыдатны для інтэграваньня, калі межы інтэграваньня імкнуцца да бясконцасьці. Аднак адмоўныя ступені x альбо любая іншая функцыя, интэгруемая на бясконцасьці, таксама могуць быць выкарыстаныя для раскладаньня. Напрыклад:
f(x) = a₂/x² + a₃/x³ ... ці:
f(x) = a₁e^-x + a₂e^-2x ...
і гэтак далей. Каэфіцыенты a_i могуць быць вынайдзеныя аналагічна раду Тэйлара:
a_i = 1/i! dⁱf(x)/df₀ⁱ
дзе f₀ - базысная функцыя раскладаньня. Каэфіцыенты раскладаньня таксама могуць быць знойдзеныя прыблізна, напрыклад, пры дапамозе мэтада найменьшых квадратаў . Зараз ўжо вельмі проста інтэграваць:
т^Ґ_a f(x)dx = т^Ґ_a a₂/x² + т^Ґ_a a₃/x³ + ... = -a₂/a - 0.5*a₃/a²...
Застаецца толькі прасуміраваць атрыманы рад з неабходнай дакладнасьцю. Вельмі важна, каб раскладаньне па адмоўных ступенях x пачыналася з x^-2 - толькі тады яго можна інтэграваць.
Бэта-функцыя ды гамма-функцыя - важныя нявідавочныя функцыі.
Бэта-функцыя вызначаецца як:
B(p,q) = т¹₀x^p-1(1-x)^q-1 dx (p>0, q>0)
Гамма-функцыя вызначаецца як:
G(s) = т^Ґ₀x^s-1*Exp(-x) dx (s>0)
Працэдура, што вылічае каэфіцыенты раскладаньня Тэйлара для (1-x)^q па x ды працэдура што вылічае бэта-функцыю з выкарыстаньнем раскладаньня Тэйлара для інтэграваньня - ў модулі Matrix.pas.