Застосування технології довгої арифметики при побудові алгоритмів дослідження лінійних систем (стр. 1 )

ЗАСТОСУВАННЯ ТЕХНОЛОГІЇ ДОВГОЇ АРИФМЕТИКИ ПРИ ПОБУДОВІ АЛГОРИТМІВ ДОСЛІДЖЕННЯ ЛІНІЙНИХ СИСТЕМ

519.852:519.876

В. І. КУДІН, В. В. ОНОЦЬКИЙ, С. І. ЛЯШКО

Резюме. Запропоновано алгоритм та комп´ютерну реалізацію методів типу Гауса та штучних базисних матриць в середовищах Мatlab та Visual С++ з використанням технології точного представлення обчислень елементів методів. Наведено результати обчислювального експерименту за згаданими методами, в якому тестові моделі систем генерувались, зокрема, на основі матриць Гільберта різної розмірності.

Для аналізу властивостей лінійних систем рівнянь (СЛАР) та нерівностей (СЛАН) з квадратною матрицею обмежень розроблено ряд точних методів[1-4]. Серед них особливе місце займають алгоритмічні схеми, що базуються на методі Гауса. Відомо, що за своїми структурними властивостями моделі СЛАР належать до некоректних. Однією з проявів некоректності є властивість поганої обумовленості [3-4]. Для тестування відомих схем розв’язання даного класу задач є розроблено ряд бібліотек моделей систем з поганообумовленими матрицями обмежень. Зокрема, до таких матриць належить матриця Гільберта.

В роботах [1-2] наведено основні співвідношення, що використані при побудові методу базисних матриць (МБМ). На основі формул зв’язку елементiв методу в cуciднiх штучних розв’язках запропоновано ітераційну процедуру знаходження рангу матриці обмежень. Встановлено умову єдиності розв´язків СЛАР.

Основні положення методу Гауса детально викладені у ряді монографій та посібниках [3-6], а тому наводитись не будуть.

В даному дослідженні авторами розроблено алгоритмічну схему проведення обчислень за схемою МБМ та Гауса з використанням технології довгої арифметики для моделей з раціональними елементами, яку реалізовано у вигляді бібліотеці “Longnum” на мові С++.

В сучасних ЕОМ, як правило, використовуються стандарті типи цілих чисел, розмір яких не перевищує 64 байта. Подолання такого апаратного обмеження можна вирішити програмним шляхом, а саме, розробкою власного типу даних. Прикладом є клас Large[5]. Бібліотека “Longnum” розроблена мовою С++ з використанням стандартної бібліотеки шаблонів STL(Standard Template Library).

Постановка задачі аналізу СЛАР

Розглянемо СЛАР виду

, (1)

де матриця розмірності , а також допоміжну СЛАР виду

, (2)

де - одинична матриця розмірності , а - вектор розмірності m, Т - знак транспонування, - рядки матриці .

Предметом дослідження буде:

- встановлення рангу системи (1)

- знаходження розв¢язків (1)

- встановлення умов існування, єдиності та неєдиності розв¢язків

- представлення в аналітичному вигляді розв¢язків системи рівнянь та нерівностей

- дослідження властивостей відповідних оптимізаційних задач.

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

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

Нехай:- елементи матриці оберненої до ; - базисний розв’язок,; - вектор розвинення вектору-нормалі обмеження за рядками базисної матриці ; - нев’язка r-го обмеження (1) в вершині. Всі введені елементи в новій базисній матриці , відмінній від одним рядком, будемо позначати рискою зверху.

Теорема 1. Між коефіцієнтами розвинення нормалей обмежень (3), цільової функції (4) за рядками штучної базисної матриці, елементами обернених матриць, базисними розв’язками, нев¢язками обмежень (1) в двох суміжних базисних матрицях мають місце такі співвідношення (3)-(6):

(3)

(4)

(5)

; (6)

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

На основі (3)-(5) будується схема визначення рангу системи (1) та розв’язку системи рівнянь, послідовними змінами базисних матриць та відповідних штучних розв¢язків.

Особливості МШБМ:

· СЛАР (1) та (2) розглядаються сумісно

· тривіальна обернена матриця та розв¢язок (2) є початковими

· проводяться заміщення нормалями обмежень (1), рядків штучної базисної матриці (2), згідно формул (3)-(6)

· максимальна кількість ітерацій по знаходженню рангу системи (при невиродженості) обмежена числом m

· ідеологія сипмлексних перетворень (3)-(6) може бути застосовувана для аналізу виродженості матриці обмежень, рангу та розв’язку СЛАР (1) при збуренні її елементів

· штучні розв¢язки, знайдені на ітераціях методу, є недопустимими для (2).

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

Наслідок 1. Матриця А основної системи (1) невироджена, якщо .

Наслідок 2. Ранг системи (1) визначається кількістю коректних заміщень рядків матриці обмежень (2) векторами нормалями (1), згідно формул (3)-(6).

Концепція представлення цілих чисел

Для реалізації довгих цілих чисел довільного розміру та відповідних раціональних чисел в С++ був використаний об’єктно-орієнтований підхід (ООП), який полягає у співставлені реальному об’єкту предметної області так званий об’єктний тип або клас об’єктів, що є узагальненням структурного типу[8].

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

В даній роботі ціле число довільного розміру запрограмовано у вигляді класу longint. Раціональне число як пара (чисельник класу longint, знаменик класу longint) запрограмоване у вигляді класу longrat. Ціле число зберігається як вектор-контейнер deque із стандартної бібліотеки шаблонів STL, довжина якого може автоматично (динамічно) змінюватися в залежності від величини числа, яке треба зберігати. Елементами вектора є 32-бітні беззнакові числа стандартного типу C++ unsigned __int32.

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

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

Так, наприклад, ціле число з діапазону від 264 до 2128-1 буде зберігатися у векторі розміру 3.

Вектор, знак числа та операції над числами такої структури оформлені у вигляді класу longint. Зокрема, в класі longint реалізовані такі операції з цілими числами: додавання, віднімання, множення та ділення з остачею, порівняння, конвертація у рядок символів типу char.

Операції ‘+’,’-’,’*’,’/’ реалізовані за класичними алгоритмами додавання, віднімання, множення, ділення в стовпчик і не виключають можливість оптимізації як за часом, так і за використаними ресурсами ЕОМ.

Оголошення класу longint

class longint

{

public:

__int8 sign;

std::deque<unsigned __int32> v;

longint();

longint(char *s1);

friend ostream& operator<<(ostream& o, longint& l);

char* text(void);

friend __int8 longiabscmp(longint& a, longint& b);

friend longint operator+(longint& a, longint& b);

friend longint operator-(longint& a, longint& b);

friend longint operator*(longint& a, longint& b);

friend longint operator/(longint& a, longint& b);

void operator+=(longint &l);

void operator-=(longint &l);

void operator*=(longint &b);

friend __int8 divmod(longint &a, longint &b, longint &l, longint &r);

friend longint ncd(longint a, longint b);

};

Представлення раціональних чисел

Раціональне число представляється як пара: чисельник та знаменник типу longint і оформлено у вигляді класу longrat. Даний клас також оснащується стандартними операціями додавання, віднімання, множення, ділення, скорочення, порівняння, представлення у вигляді десяткового числа заданої точності, конвертація у тип double, конвертація у рядок символів типу char. Операції ‘+’,’-’,’*’,’/’ побудовані з використанням відповідних операцій над числами типу longint. Пошук найбільшого спільного дільника для операції скорочення здійснюється алгоритмом Евкліда[7].

Данні класи були відкомпільовані у вигляді динамічної бібліотеки longnum.dll та протестовані для точного розв’язування систем лінійних алгебраїчних рівнянь.

Оголошення класу longrat

class longrat

{

public:

longint num;

longint denom;

longrat():num(),denom("1"){}

longrat(char *s);

longrat(char *s1,char *s2):num(s1),denom(s2) {reduce(); };

friend ostream& operator<<(ostream &f, const longrat &a);

void text(char *s);//return s as 'p/q';

friend longrat operator+(longrat &a, longrat &b);

friend longrat operator-(longrat &a, longrat &b);

friend longrat operator*(longrat &a, longrat &b);

friend longrat operator/(longrat &a, longrat &b);

void operator+=(longrat &a);

void operator-=(longrat &a);

void operator*=(longrat &a);

void operator/=(longrat &a);

char* decimal(unsigned __int32 size);//return decimal s;

operator double();

friend __int8 longrabscmp(longrat &a, longrat &b);

void reduce(void);

};

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

Алгоритм

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

Крок 1. Проводимо симплексні ітерації по заміщенню рядків базисної матриці системи (2) нормалями обмежень системи (1), згідно співідношень (5)-(9).

Знаходимо відповідні елементи методу: вектори розвинення за рядками базисних матриць обмежень (2), обернену базисну матрицю, штучні базисні розв’язки , де - номер ітерації.

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

Крок 3. Якщо кількість ітерацій, для яких , рівна m, то переходимо на наступний крок. В супротивному на передостанній крок.

Крок 4. Знаходимо єдиний розв¢язок згідно співвідношення: .

Крок 5. Виконання умови означає порушення умови єдиності розв'язку і потребує подальшого аналізу розв¢язності задачі.

Останній крок. Формування вихідної інформації за результатами аналізу (1) у вигляді масиву елементів типу longrat.

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

Розв’язування СЛАР з використанням бібліотеки longnum

Було розглянуто дві СЛАР з поганобумовленими матрицями, а саме:
матриця Гілберта з елементами [6] та

матриця з елементами .

Матриця розглядалася з такими варіантами правих частин:

1) ;

2) ;

3) .

Для матриці вектор правих частин визначається співвідношенням:

.

СЛАР розв’язувалися методами Гауса та МШБМ.

В результаті експериментів для СЛАР з матрицею Гільберта розмірності та одиничною правою частиною отримано точні розв’язки (таблиця 1) як методом Гауса, так і методом штучних базис­них матриць, які співпадають. При цьому час виконання на ЕОМ (з процесо­ром Athlon 1700+ з частотою 1400 МГц, оперативною пам’яттю 256 Мбайт) складав 6788.29 та 3724.21 секунд для методів МШБМ та Гауса відповідно.

Точний розв’язок СЛАР з матрицею Гілберта , розмірності

Таблиця 1

Компоненти розв’язку в точному вигляді	Компоненти розв’язку з плаваючою крапкою
-100/1	-100
999900/1	999900
-/1	-2.49875e+009
/1	2.77389e+012
-/1	-1.73091e+015
/1	6.90632e+017
-/1	-1.91152e+020
/1	3.88194e+022
-/1	-6.02671e+024
/1	7.38011e+026
-/1	-7.30631e+028
/1	5.96521e+030
-/1	-4.08286e+032
/1	2.37506e+034
-/1	-1.18802e+036
/1	5.16127e+037
-/1	-1.96451e+039
/1	6.60116e+040
-/1	-1.97138e+042
/1	5.26375e+043
-/1	-1.2633e+045
/1	2.7383e+046
-/1	-5.38381e+047
/1	9.63896e+048
-/1	-1.57704e+050
/1	2.36556e+051
-/1	-3.26279e+052
/1	4.14943e+053
-/1	-4.8777e+054
/1	5.31211e+055
-/1	-5.37113e+056
/1	5.052e+057
-/1	-4.42839e+058
/1	3.62364e+059
-/1	-2.77227e+060
/1	1.98585e+061
-/1	-1.33371e+062
/1	8.40849e+062
-/1	-4.9822e+063
/1	2.77739e+064
-/1	-1.45813e+065
/1	7.21605e+065
-/1	-3.36913e+066
/1	1.48522e+067
-/1	-6.18638e+067
/1	2.43636e+068
-/1	-9.07764e+068
/1	3.20163e+069
-/1	-1.06943e+070
/1	3.38468e+070
-/1	-1.0154e+071
/1	2.88849e+071
-/1	-7.79381e+071
/1	1.9952e+072
-/1	-4.84706e+072
/1	1.11763e+073
-/1	-2.44624e+073
/1	5.08296e+073
-/1	-1.00269e+074
/1	1.87778e+074
-/1	-3.33827e+074
/1	5.63316e+074
-/1	-9.02127e+074
/1	1.37081e+075
-/1	-1.97589e+075
/1	2.70077e+075
-/1	-3.49934e+075
/1	4.29603e+075
-/1	-4.99469e+075
/1	5.49616e+075
-/1	-5.72049e+075
/1	5.62744e+075
-/1	-5.22796e+075
/1	4.58243e+075
-/1	-3.78578e+075
/1	2.9445e+075
-/1	-2.15331e+075
/1	1.47852e+075
-/1	-9.51658e+074
/1	5.7319e+074
-/1	-3.2242e+074
/1	1.68999e+074
-/1	-8.23379e+073
/1	3.71829e+073
-/1	-1.5514e+073
/1	5.95865e+072
-/1	-2.09793e+072
/1	6.73811e+071
-/1	-1.96296e+071
/1	5.15213e+070
-/1	-1.20852e+070
/1	2.5087e+069
-/1	-4.55265e+068
/1	7.11137e+067
-/1	-9.36808e+066
/1	1.01206e+066
-/1	-8.60957e+064
/1	5.40786e+063
-/1	-2.22981e+062
/1	4.52743e+060

Для СЛАР з матрицею коефіцієнтів проведені розрахунки з використанням методу Гауса та МШБМ. Результати обчислювального експерименту наведені в таблиці 2.