Размещено на http://www.allbest.ru/

1

Національна академія наук України

Інститут кібернетики імені В.М.Глушкова

УДК 519.6: 513.3

Автореферат дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

Алгоритми для систем З ТЕПЛІЦЕВИМИ -МАТРИЦЯМИ та ЇХ ЗАСТОСУВАННЯ

01.05.02 - математичне моделювання та обчислювальні методи

Ковальчук Ольга Ярославівна

Київ - 2005

Дисертацією є рукопис.

Робота виконана в Тернопільському державному економічному університеті

Міністерства освіти і науки України

Науковий керівник: доктор фізико-математичних наук, професор

Недашковський Микола Олександрович,

завідувач кафедри автоматизованих систем і

програмування Тернопільського державного

економічного університету.

Офіційні опоненти: доктор фізико-математичних наук

Хіміч Олександр Миколайович,

завідувач відділу інституту кібернетики

імені В.М. Глушкова НАН України,

старший науковий співробітник,

Доктор фізико-математичних наук, професор

Григорків Василь Степанович,

завідувач кафедри економіко-математичного

моделювання Чернівецького національного

університету імені Ю.Федьковича.

Провідна установа: Львівський національний університет імені І.Франка, факультет прикладної математики та інформатики, кафедра теорії оптимальних процесів.

Захист відбудеться “ 23 ” грудня 2005 р. об 11⁰⁰ годині на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики імені В.М.Глушкова НАН України за адресою:

03680 МСП Київ-187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві інституту.

Автореферат розісланий “ 9 ” листопада 2005 р.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. При дослідженнях математичних моделей з використанням методів лінійної алгебри традиційним і завжди актуальним є етап знаходження розв'язків систем лінійних алгебраїчних рівнянь (СЛАР). Ще зовсім недавно ЕОМ використовувалися в основному для розв'язування різних класів таких задач з початковими даними чисельного характеру.

Останнім часом при проведенні досліджень за допомогою математичного моделювання у фізиці, електротехніці та інших областях науки і техніки виник також стійкий інтерес до використання комп'ютерів для символьних перетворень та одержання аналітичних розв'язків, хоча й у “чистій математиці” завжди гостро відчувалась необхідність у використанні ЕОМ для виконання найбільш трудомісткої чорнової роботи. Однією з перших удалих спроб реалізації такого підходу було створення мови “Аналітик” для машин серії “МИР” в Інституті кібернетики НАН України ще в 60-х роках ХХ ст.

Сьогодні існують й успішно розвиваються декілька напрямів і концепцій для виконання символьних перетворень. З комп'ютерних систем універсального характеру найбільш відомими є Reduce, muMATH, MATHEMATICA, MAPLE, MatLab, MathCad і DERIVE. Їх можна використовувати для розв'язування різних задач комп'ютерної алгебри, у тому числі і для знаходження розв'язків систем лінійних алгебраїчних рівнянь. Але цей розділ у названих комп'ютерних системах ще не настільки добре розвинутий, як відповідні методи для числових систем.

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

Такими дослідженнями займались Д.К.Фадєєв, В.М.Фадєєва, С.А.Абрамов, В.М.Кублановська, М.О.Недашковський, Г.І.Малашонок, J.Lipson, J.Smit, D.Mazykelli, P.T.Moenk, J.Carter, S.Cabay, B.Domzy, Е.H.Bareiss, M.T.Macclellan та інші автори.

Серед вказаних досліджень не одержали належного розвитку СЛАР з тепліцевими _матрицями, тобто матрицями, в яких на кожній діагоналі, розташованій паралельно до головної, стоять однакові елементи. Такі матриці повністю визначаються елементами першого стовпця та першого рядка.

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

З тепліцевими тісно пов'язаний ще один клас матриць - ганкелеві. Простою перестановкою стовпців (стрічок) в оберненому порядку тепліцеву (ганкелеву) матрицю можна перетворити в дві різні ганкелеві (тепліцеві) матриці. Тому для розв'язування СЛАР як з ганкелевими, так і з тепліцевими матрицями можна використовувати одні і ті ж обчислювальні схеми.

Інтерес до теорії тепліцевих і ганкелевих матриць, елементами яких є дійсні числа, і розв'язування СЛАР з цими матрицями завдяки їх широкому застосуванню не послаблюється ще з початку двадцятого століття. Найбільш вагомий внесок у розвиток даної теорії зробили W.Trench, R.Blahut, В.В.Воєводін, Є.Є.Тиртишніков, І.С.Іохвідов та інші.

Оскільки СЛАР з тепліцевими _матрицями є недостатньо вивченими, актуальною задачею є розробка ефективних алгоритмів їх розв'язування на основі використання специфічних властивостей цих матриць.

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

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

Ці дослідження є важливими для розв'язування як вказаних вище прикладних задач, так і оптимізаційних задач, в яких цільова функція залежить від розв'язків СЛАР з тепліцевими _матрицями, тобто є функцією параметра . Такими є, наприклад, задачі знаходження розв'язків СЛАР із заданими властивостями: мінімальний за нормою розв'язок, мінімально віддалений від заданого розв'язку тощо.

Дана робота присвячена побудові ефективних алгоритмів розв'язування тепліцевих та ганкелевих СЛАР з _матрицями і виконана впродовж 2000-2005 років на кафедрі автоматизованих систем і програмування Тернопільського державного економічного університету (м.Тернопіль).

Зв'язок роботи з науковими програмами, планами, темами. Базовою для даних дисертаційних досліджень стала комплексна науково-дослідна робота Центральної науково-дослідної лабораторії Тернопільського державного медичного університету імені І.Я.Горбачевського на тему “Структурно-функціональне обгрунтування магнітолазерного впливу для профілактики і корекції уражень товстої кишки” (номер державної реєстрації 0101U001312), яка виконувалася на замовлення та за фінансової підтримки МОЗ України.

Мета і завдання дослідження. Метою даної дисертаційної роботи є побудова та обгрунтування ефективних алгоритмів розв'язування СЛАР з тепліцевими та ганкелевими _матрицями. Для досягнення мети були поставлені такі задачі:

- побудова ефективних алгоритмів розв'язування СЛАР з тепліцевими _матрицями, елементами яких є алгебраїчні поліноми;

- розробка швидких алгоритмів розв'язування СЛАР з блочно-тепліцевими _матрицями;

- розробка ефективних алгоритмів розв'язування тепліцевих та ганкелевих СЛАР з тригонометричними _матрицями;

- побудова моделей для реалізації алгоритмів розв'язування СЛАР з блочно-тепліцевими _матрицями з поліноміальними елементами на багатопроцесорних обчислювальних системах;

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

Методи дослідження. Знаходження розв'язків систем лінійних алгебраїчних рівнянь з тепліцевими (ганкелевими) _матрицями базується на теорії тепліцевих матриць, швидкому перетворенні Фур'є, теорії ланцюгових дробів. Для відшукання розв'язків таких СЛАР розроблено поліноміальні модифікації відповідних алгоритмів лінійної алгебри для числових матриць з дійсними та комплексними елементами: Тренча, Левінсона, Тиртишнікова.

Наукова новизна одержаних результатів, що виносяться до захисту:

- на основі економічних схем знаходження оберненої матриці розроблено алгоритми, які узагальнюють числові методи лінійної алгебри для тепліцевих (ганкелевих) матриць з дійсними та комплексними елементами, на випадок СЛАР з тепліцевими (ганкелевими) _матрицями. Зроблено аналіз оцінок (зокрема і похибок заокруглення) створених алгоритмів;

- розроблено схему розв'язування СЛАР з блочно-тепліцевими (ганкелевими) матрицями. Для побудованих алгоритмів досліджено їх характеристики;

- побудовано моделі для реалізації алгоритмів розв'язування СЛАР з блочно-тепліцевими _матрицями з поліноміальними елементами на багатопроцесорних обчислювальних системах;

- проведено аналіз оцінок (пам'яті комп'ютера, числа арифметичних операцій, комп'ютерного часу, похибок розв'язку СЛАР з тепліцевими _матрицями) для побудованих алгоритмів;

- для математичних моделей імунного захисту організму та щільності кісткової тканини досліджено стійкість розв'язків. Комп'ютерні алгоритми, розроблені на основі цих моделей, впроваджено в навчальний процес у Тернопільському державному медичному університеті імені І.Я.Горбачевського.

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

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

Наукове значення роботи. Поряд із важливістю досліджень стосовно розв'язків тепліцевих (ганкелевих) СЛАР з _матрицями отримані результати можуть бути застосовані при розв'язуванні задач оптимізації, наприклад, обчисленні найменшого за нормою або найменш віддаленого від заданї точки розв'язку СЛАР з тепліцевою _матрицею, а також деяких задач лінійного параметричного програмування.

Практичне значення отриманих результатів.

Для математичних моделей імунного захисту організму та щільності кісткової тканини досліджено стійкість розв'язків, і на їх основі розроблено алгортми, які впроваджено в навчальний процес у Тернопільському державному медичному університеті імені І.Я.Горбачевського.

Особистий внесок. Основні результати, що включені в дисертацію, отримані автором особисто. У праці [5], яка опублікована спільно з науковим керівником, М.О.Недашковському належить ідея використання гіллястих ланцюгових дробів для побудови алгоритмів розв'язування СЛАР з тепліцевими _матрицями, результати щодо розв'язування СЛАР з блочно-трьохдіагональними матрицями та матричних поліноміальних рівнянь. У працях [6-13] та [16-18], написаних у співавторстві, автору дисертаційної роботи належать усі теоретичні та практичні результати, крім постановок задач та ідей теоретичних досліджень.

Апробація результатів дисертації. Результати роботи доповідались на Міжнародній науковій конференції “Розробка та застосування математичних методів у науково-технічних дослідженнях” (8-10 жовтня 1998 р., м.Львів), VIIІ та IХ Міжнародних наукових конференціях імені академіка М.Кравчука (11-14 травня 2000 р. та 16-19 травня 2002 р., м.Київ), ІІ Міжнародній науково-практичній конференції “Інформаційні технології в охороні здоров'я та практичній медицині” (19-21 червня 2002 р., м.Київ), XLV підсумковій (міжрегіональній) науково-практичній конференції (7 червня 2002 р., м.Тернопіль), IV Міжнародній науково-практичній конференції студентів, аспірантів та молодих вчених (1-3 липня 2002 р., м.Київ), VІ Кримській Міжнародній Математичній школі “Метод функцій Ляпунова та його застосування” (МФЛ-2002, Крим, Алушта, 8-15 вересня 2002 р.), Міжнародній науковій конференції “Шості Боголюбівські читання” (26-30 серпня 2003 р., м.Чернівці), Міжнародній конференції “Прогнозування та прийняття рішень в умовах невизначеності” (8-12 вересня 2003 р., Київ-Алушта), Міжнародному науково-практичному семінарі “Прогнозування та прийняття рішень в умовах невизначеності” (25-30 травня 2004 р., м.Тернопіль).

Публікації. За матеріалами проведених досліджень опубліковано 19 наукових робіт, у тому числі 5 статей - у виданнях з переліку, затвердженому ВАК України.

Структура та обсяг роботи. Дисертація складається із вступу, чотирьох розділів, висновків, списку використаних джерел, що містить 155 найменувань, та додатків. Загальний обсяг дисертаційної роботи викладено на 190 сторінках, обсяг основного тексту - 158 сторінок. Робота включає 4 рисунки та 1 таблицю.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

Перший розділ присвячено огляду літературних джерел за тематикою дисертації. Викладено відомі наукові результати та підходи до розв'язування систем лінійних алгебраїчних рівнянь з тепліцевими та ганкелевими матрицями. Обгрунтовано вибір подальших напрямів досліджень, пов'язаних з побудовою економічних алгоритмів для розв'язування СЛАР з тепліцевими та ганкелевими _матрицями.

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

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

На k-му кроці алгоритму виконується порядку операцій множення і операцій додавання-віднімання. Загальні затрати складають з точністю до головного члена операцій множення і операцій додавання-віднімання. Операції ділення в головний член не входять.

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

У підрозділі 2.2 запропоновано алгоритми розв'язування лінійних алгебраїчних рівнянь вигляду

, (2)

де

- (3)

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

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

+,(4)

де

,

.

Рекурентні співвідношення (4) служать для обчислення вектора

,

коли вже визначені невідомі системи рівнянь .

Якщо проводити обчислення за формулою (4) з використанням ЕОМ, виконуючи лише операції множення та додавання многочленів, може виникнути так зване “розбухання” проміжних даних і порядок поліномів в обчисленнях буде наростати із швидкістю , де k - порядок розв'язуваної відсіченої системи. Для уникнення цього явища проведено додаткові дослідження.

та шукаються у вигляді відношення двох поліномів з невідомими коефіцієнтами

=+ ,

=+.

Теорема 1. Якщо в процесі реалізації алгоритму (4) всі головні мінори тепліцевої матриці не дорівнюють нулю, то та поліноми є дільниками многочленів

і .

У загальному випадку .

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

У підрозділі 2.3 узагальнено алгоритм для тепліцевих матриць з дійсними та комплексними елементами на випадок розв'язування системи з тригонометричною _матрицею. Обчислювальна схема базується на відшуканні елементів першого та останнього стовпців оберненої матриці, через які повністю визначається .

Розв'язується СЛАР вигляду (2) з тепліцевою ?_матрицею (3), де елементи та вектора є тригонометричними поліномами степеня l

.

Розглядаються відсічені системи

, . (5)

Нехай та , - відповідно перший та останній стовпці оберненої матриці для кожної з відсічених систем (5).

Вектор співпадає з , отже, є шуканим розв'язком . визначається як . Якщо вже відомий вектор при , то будемо шукати у вигляді

.(6)

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

Для реалізації даного алгоритму на комп`ютері достатньо виконати порядку операцій множення та операцій додавання-віднімання.

Вектор-розв'язок може бути отриманий на місці вектора-правої частини.

Підрозділ 2.4 присвячено побудові алгоритмів розв'язування СЛАР із ганкелевими матрицями з алгебраїчними поліноміальними елементами

де, (7)

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

Припускається, що всі ведучі мінори ?_матриці відмінні від нуля. Якщо для обчислення оберненої до ганкелевої ?-матриці використовувати алгоритми, розроблені для тепліцевих ?-матриць, доведеться накладати додаткові умови, вимагаючи, щоб усі мінори утвореної тепліцевої ?_матриці були відмінними від нуля. Тому побудовано аналог числового алгоритму для ганкелевих ?_матриць, який відповідає деякому компактному способу задання матриці .

За допомогою послідовного виключення елементів матрицю (7) зведено до трикутного вигляду. Нехай , , де - одинична матриця. При обчислюються матриці і , які задовольняють співвідношенню

,

де,

(8)

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

,(9)

де ,

, .

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

При даних обмеженнях на матрицю обернена матриця задається в такому вигляді

,(10)

де,

а величини і визначаються таким чином:

, .

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

Якщо ввести позначення , , тоді шуканий алгоритм можна записати в такий спосіб:

для

,, , ;

для

,

, ,

,(11)

.

Реалізація формул (11) потребує виконання операцій множення і стільки ж операцій додавання-віднімання. При цьому, окрім інформації про ганкелеву матрицю , треба запам'ятати на комп'ютері два вектори довжиною не більше . Обернена матриця, отримана за формулою (10), є ганкелевою. За допомогою перестановки стовпців або рядків її зведено до відповідної тепліцевої матриці . Для виконання таких перестановок використано алгоритм із заміщенням, який потребує обчислень значень відповідних підстановок з використанням додаткової памяті комірок. Шуканий розв'язок можна отримати, використавши швидке перетворення Фур'є, за операцій комплексного множення і операцій комплексного додавання-віднімання.

Підрозділ 2.5 присвячено побудові послідовних та паралельних моделей обчислень з метою зменшення часу розв'язування задачі на багатопроцесорному комп'ютері. При врахуванні обмежень можливостей і ресурсів з певним режимом роботи багатопроцесорного комп'ютера алгоритми розв'язування СЛАР з тепліцевими матрицями залежать від його структури та архітектури.

У підрозділі 2.6 досліджено оцінки характеристик розроблених алгоритмів розв'язування СЛАР з тепліцевими _матрицями.

У третьому розділі розроблено ефективні алгоритми розв'язування СЛАР з блочно-тепліцевими _матрицями, запропоновано моделі для реалізації алгоритмів розв'язування СЛАР з блочно-тепліцевими _матрицями на багатопроцесорних обчислювальних системах, обгрунтовано розроблені алгоритми розв'язування СЛАР з використанням гіллястих ланцюгових дробів.

Розглядається задача розв'язування СЛАР вигляду (2), де - блочно-тепліцева матриця, яка складається з квадратних блоків , . В ній кожен блок - це -матриця, елементами якої є алгебраїчні поліноми порядку .

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

для

;

для

,

,

.(12)

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

У загальному випадку .

Підрозділ 3.3 присвячено побудові алгоритмів розв'язування СЛАР з тепліцевими _матрицями за допомогою гіллястих ланцюгових дробів.

Означення 1. Нескінченним гіллястим ланцюговим дробом (ГЛД) називається композиція нескінченної кількості дробово-лінійних перетворень вигляду

.

Скінченний дріб

називається м підхідним дробом нескінченного ГЛД.

Теорема 3. Композиція дробово-лінійних композицій

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

Багато алгоритмів із достатньо складною структурою можуть бути подані ланцюговими дробами вигляду

.

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

Матриця розбивається на блоки і система (2) записується у вигляді

.

Розв'язок обчислюється в такий спосіб:

.

Четвертий розділ присвячено застосуванню тепліцевих _матриць у математичному моделюванні, зокрема в медичних задачах.

Досліджено стійкіть розв'язків математичної моделі імунного захисту.

У підрозділі 4.5 досліджено щільність кісткової тканини. Визначено кількість трабекулярної структури із застосуванням методів стереології. Такі методи використовують точки та лінії, проведені між структурними межами фаз кісткової тканини, і з допомогою комп'ютерних алгоритмів дають можливість отримувати якісне 3-вимірне зображення.



Рис. 1 Трабекула

Береться до уваги міра фракції (інверсія пористості об'єму) кістки - відношення перетинів сітки в межах кістки до загальної кількості перетинів сітки та кількість перетинів між кісткою та найближчим місцем сутності (на рис. 1 білий колір). Ця величина - фактично функція орієнтації, оскільки сітки обертаються від 0 до 360 градусів і перетинаються, як показано на рисунку, утворюючи еліпс. Ці виміри дають можливість оцінити відстані між перетинами кісткового мозку і вирахувати ширину трабекули. Окрім статистичних експериментальних підходів встановлення співвідношення функції та структури кістки є також аналітичні обчислювальні моделі. Найбільш відомими та простими з них є моделі Реусса та Войта, в яких припускається, що напруженість на всіх рівнях мікроструктури кістки однакова. Якщо виконувати інтеграцію об'єму кожної мікроструктури кістки, можна отримати усереднену матрицю, яка виражає частку об'єму кістки на діагоналі

,

де - матриця ефективної інверсії жорсткості, - матриця інверсії жорсткості на -й стадії.

ВИСНОВКИ

Дисертаційна робота присвячена побудові алгоритмів розв'язування СЛАР з тепліцевими -матрицями, елементами яких є алгебраїчні і тригонометричні поліноми. Розроблені алгоритми можуть бути застосовані в математичному моделюванні при розгляді прикладних задач економіки, медицини, механіки, коли виникає необхідність розв'язувати і досліджувати розв'язки СЛАР з тепліцевими -матрицями.

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

В роботі одержано такі основні резуьтати:

- розроблено та обгрунтовано ефективні алгоритми, які узагальнюють числові методи лінійної алгебри для тепліцевих (ганкелевих) матриць з дійсними та комплексними елементами, що базуються на економічних схемах знаходження оберненої матриці, на випадок розв'язування СЛАР з тепліцевими (ганкелевими) ?_матрицями. Проведено аналіз оцінок характеристик створених алгоритмів;

- запропоновано схему розв'язування блочно-тепліцевих (блочно_ганкелевих) СЛАР з тригонометричними елементами порядку l;

- створено моделі для реалізації алгоритмів розв'язування СЛАР з блочно_тепліцевими -матрицями з поліноміальними елементами на багатопроцесорних обчислювальних системах;

- розроблено та обгрунтовано алгоритми розв'язування тепліцевих та ганкелевих СЛАР з тригонометричними _матрицями;

- здійснено аналіз похибок заокруглення при реалізації запропонованих алгоритмів на ЕОМ;

- запропоновано алгоритм розв'язування систем лінійних алгебраїчних рівнянь з тепліцевими _матрицями за допомогою гіллястих ланцюгових дробів;

- для математичних моделей імунного захисту організму та щільності кісткової тканини досліджено стійкість розв'язків, і на їх основі розроблено алгортми, які впроваджено в навчальний процес у Тернопільському державному медичному університеті імені І.Я.Горбачевського.

ОСНОВНІ РЕЗУЛЬТАТИ ДИСЕРТАЦІЇ ОПУБЛІКОВАНО У ТАКИХ ПРАЦЯХ:

1. Ковальчук О.Я. Поліноміальний аналог методу Левінсона для клітково-тепліцевих матриць // Наукові записки. Серія: математика і фізика.-Тернопільський педуніверситет імені Володимира Гнатюка, 1998. - №1(11)

2. Ковальчук О.Я., Іваницький Р.І. Обчислювальні алгоритми з тепліцевими -матрицями // Наукові записки. Серія: математика і фізика.-Тернопільський педуніверситет імені Володимира Гнатюка, 1998. - №1(11). - С. 39-41.

3. Ковальчук О.Я. Комп'ютерні моделі розв'язання великих задач лінійної алгебри на багатопроцесорних обчислювальних системах // Вісник Тернопільської академіїї народного господарства. Серія: економіко-математичне моделювання. - 1998. - №2. - С. 82-92.

4. Ковальчук О.Я. Алгоритми розв'язання задач з тепліцевими _матрицями // Вісник державного університету “Львівська політехніка”. Серія: прикладна математика. Том 2. Математика і теоретична фізика. Чисельні методи. - 1998. - № 337. - С. 326-328.

5. Ковальчук О.Я., Недашковский Н.А. Решение матричных уравнений ветвящимися цепными дробями // Кибернетика и системный анализ. - 2004. - №1.- С. 22-33.

6. Марценюк В.П., Жулкевич І.В., Ковальчук О.Я. Про нелінійну динамічну систему реконструкції кісткової тканини // Вісник Київського університету. Серія: фізико-математичні науки. - 2001. - Вип. 4. - С. 292-298.

7. Марценюк В.П., Кравець Н.О., Ковальчук О.Я., Семенець А.В., Кульчицький В.І., Лашкевич І.М. Системи підтримки рішень в медико-біологічних дослідженнях. - В зб. наукових праць “Здобутки клінічної та експериментальної медицини”. - Тернопіль: “Укрмедкнига”, 2002. - Вип. 7.

8. Марценюк В.П., Ковальчук О.Я., Сверстюк А.С., Семенець А.В. Задачі оптимізації в моделях популяційної динаміки. - International conference “Problems of decision making under uncertainties”, September 8-12, 2003.

9. Марценюк В.П., Гудима А.А., Кравець Н.О., Ковальчук О.Я., Семенець А.В. Комп'ютерно-математичне моделювання процесів з післядією в медицині // ІІ Міжнародна науково-практична конференція “Інформаційні технології в охороні здоров'я та практичній медицині”. - В зб. наук. праць. - Київ. - 2002. - С. 86-88.

10. Марценюк В.П., Кравець Н.О., Ковальчук О.Я. Про збіжність еволюційних алгоритмів у задачах медичної діагностики // Штучний інтелект, №4, 2002. - С. 37-42.

11. Марценюк В.П., Ладика Р.Б., Ковальчук О.Я. Про оптимізаційний підхід в задачі вибору схеми хіміотерапії // Вісник Харківського національного університету. Серія: математика, прикладна математика і механіка. - 2003, том 582, вип. 52. - С. 71-80.

12. Марценюк В.П., Кравец Н.О., Ковальчук О.Я. Оптимальное управление режимами терапии с сохранением клеточных циклов // Штучний інтелект. - 2003. - №3. - С. 150-160.

13. Марценюк В.П., Ковальчук О.Я., Куляс А.І. Про стійкість розв'язків математичної моделі імунного захисту // Комп'ютерні засоби, мережі та системи, 2003. - №2. - С. 106-112.

14. Ковальчук О.Я. Розв'язування систем лінійних алгебраїчних рівнянь з ганкелевими -матрицями з поліноміальними елементами // VII Міжнародна Наукова Конференція ім. акад. М.Кравчука (Київ, 11-14 травня 2000р.) - С. 299.

15. Ковальчук О.Я. Розв'язування систем лінійних алгебраїчних рівнянь з несиметричними тепліцевими -матрицями // ІХ міжнародна наукова Конференція ім. акад. М.Кравчука (Київ, 16-19 травня 2002р.) - С.304.

16. Марценюк В.П., Ковальчук О.Я., Кравець Н.О., Семенець А.В. Про ідентифікацію параметрів в медико-біологічних системах // Системний аналіз та інформаційні технології: Тези доповідей учасників IV Міжнародної науково-практичної конференції студентів, аспірантів та молодих вчених (1-3 липня 2002 р., м.Київ). - К.: ІВЦ “Видавництво “Політехніка”, 2002. - С. 45.

17. Марценюк В.П., Ковальчук О.Я., Семенец А.В. Условия устойчивости в системе иммунной защиты организма // Тезисы докладов участников Шестой Крымской Международной Математической школы “Метод функций Ляпунова и его приложения” (8-15 сентября 2002 г, г.Алушта). - С. 95.

18. Марценюк В.П., Ковальчук О.Я. Перевірка необхідних умов оптимальності в схемі хіміотерапії // Міжнародна наукова конференція “Шості Боголюбовські читання” (Чернівці, 26-30 серпня 2003 р.). Тези доповідей. - С. 140.

19. Ковальчук О.Я. Застосування СЛАР з тепліцевими _матрицями в математичному моделюванні процесів і явищ різної природи // Міжнародна науково-практична конференція “Наукові дослідження - теорія та експеримент, 2005” (Полтава, 16-20 травня 2005 р.) - С. 32-35.

Ковальчук О.Я. Алгоритми для систем з тепліцевими -матрицями та їх застосування. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.02. - математичне моделювання та обчислювальні методи. - Інститут кібернетики імені В.М.Глушкова НАН України, Київ, 2005. алгоритм обчислення система тепліцева матриця

У дисертаційній роботі вперше запропоновано ефективні алгоритми розв'язування СЛАР з ганкелевими та тепліцевими _матрицями з поліноміальними та тригонометричними елементами. Побудовано послідовні та паралельні моделі розв'язування систем лінійних алгебраїчних рівнянь з блочно-тепліцевими _матрицями. Для одержаних алгоритмів проведено зворотний аналіз похибок заокруглення. В результаті встановлено, що комп'ютерній реалізації методів для тепліцевих матриць відповідають обмежені еквівалентні збурення, які при використанні режиму для скалярних добутків не залежать від порядку системи. На основі розроблених обчислювальних алгоритмів з використанням засобів об'єктно-орієнтованого програмування створену програму. Проведено обчислювальні експерименти, які підтверджують ефективність запропонованих обчислювальних схем. Розроблені алгоритми впроваджено у навчальний процес Тернопільського державного медичного університету імені І.Я.Горбачевського у вигляді програм.

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

Ковальчук О.Я. Алгоритмы для систем с теплицевыми -матрицами и их применение. - Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02. - математическое моделирование и вычислительные методы. - Институт кибернетики имени В.М.Глушкова НАН Украины, Киев, 2005.

В диссертационной работе впервые разработаны эффективные алгоритмы решения систем линейных алгебраических уравнений с теплицевыми _матрицами с полиномиальными и тригонометрическими элементами. Вычислительние схемы поиска решений СЛАР базируются на числовом аналоге определения обратной матрицы через элементы ее первого и последнего столбцов. Для реализации предложенных алгоритмов на компьютере необходимо выполнить порядка арифметических операций и обеспечить запоминание, кроме элементов начальной матрицы, двух векторов длиной не больше n, координатами которых есть полиномы степеня не выше .

Разработан алгоритм решения систем линейных алгебраических уравнений с генкелевыми _матрицами. С помощью последовательного исключения элементов матрица сводится к треугольному виду и за арифметических операций вычисляется . Решение получаем с использованием быстрого преобразования Фурье, выполнив порядка арифметических операций.

Построены последовательные и параллельные модели решения систем линейных алгебраических уравнений с блочно-теплицевыми _матрицами на многопроцессорных вычислительных системах. Предложен алгоритм решения СЛАР с помощью ветвящихся цепных дробей.

Получены и проанализированы оценки характеристик (памяти компьютера, числа арифметических операций, компьютерного времени) для построенных алгоритмов. Исследована устойчивость моделей имунной системы и реконструкции костной ткани. На их основе разработаны компьютерные алгоритмы и внедрены в учебный процесс Тернопольского государственного медицинского университета имени И.Я.Горбачевского.

Для построенных алгоритмов проведен обратный анализ ошибок округления. В результате установлено, что компьютерной реализации методов для теплицевых _матриц отвечают ограниченные эквивалентные возмущения, которые при использовании режима для скалярных произведений не зависят от порядка системы. На основе разработанных вычислительных алгоритмов с использованием средств объектно-ориентированного программирования создана программа. Проведены вычислительные эксперименты, которые подтверждают эффективность предложенных вычислительных схем.

Ключевые слова: -матрица, теплицева матрица, ганкелева матрица, алгебраический полином, тригонометрический полином, ошибка округления, ветвящаяся цепная дробь, параллельные модели, блочный алгоритм.

Kovalchuk O.Ya. Algorithms for Systems with Toeplitz _Matrices and their Application. - Manuscript.

Candidate of Phys. & Math Sci. Degree Thesis. Speciality 01.05.02 - Mathematical Modelling and Computation Methods. V.M.Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, 2005.

In the thesis new effective algorithms of solution of system of linear algebraic equations with Hankel matrices and Toeplitz _matrices with polynomical and trigonometrical elements for the first time are developed. Parallel and consecutive models of systems of the linear algebraic equations with block-Toeplitz _matrices solving are constructed. For the received algorithms the return analysis of errors of rounding off has been made. It is as a result established, that computer realization of methods for Toeplitz _matrices correspond the limited equivalent indignations which at the use of a mode for scalar products do not depend on the system's order. On the basis of the developed computing algorithms with use of means of object-oriented programming the program is created. Computing experiments which confirm efficiency of the offered computing schemes are made. The developed algorithms are introduced into the educational process of the I.Ya.Horbachevsky Ternopil State Medical University in the form of programs.

Keywords: _matrices, Toeplitz matrices, Hankel matrices, algebraic polynom, trigonometrical polynom, round error, branched continued fraction, parallel models, block algorithm.

Размещено на Allbest.ru