Алгоритм оцінювання розв’язків деяких погано обумовлених систем лінійних алгебраїчних рівнянь
Пропонується алгоритм оцінювання невідомих значень системи лінійних алгебраїчних рівнянь (СЛАР), особливості якої є погана обумовленість, рівність (по модулю) між собою невідомих, наявність завад (шуму), які діють на вільні члени СЛАР. Зазначений алгоритм базується на можливості побудови певної суку...
Gespeichert in:
| Datum: | 2018 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Schriftenreihe: | Компьютерная математика |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/161894 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Алгоритм оцінювання розв’язків деяких погано обумовлених систем лінійних алгебраїчних рівнянь / В.І. Масол, Є.О. Шевченко // Компьютерная математика. — 2018. — № 2. — С. 135-144. — Бібліогр.: 6 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-161894 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1618942019-12-26T01:25:56Z Алгоритм оцінювання розв’язків деяких погано обумовлених систем лінійних алгебраїчних рівнянь Масол, В.І. Шевченко, Є.О. Теория и методы оптимизации Пропонується алгоритм оцінювання невідомих значень системи лінійних алгебраїчних рівнянь (СЛАР), особливості якої є погана обумовленість, рівність (по модулю) між собою невідомих, наявність завад (шуму), які діють на вільні члени СЛАР. Зазначений алгоритм базується на можливості побудови певної сукупності СЛАР з суттєво меншим числом обумовленості, ніж числом обумовленості початкової системи, з подальшою статистичною обробкою розв’язків цих СЛАР. Предлагается алгоритм оценивания неизвестных значений системы линейных алгебраических уравнений (СЛАУ), особенности которых – плохая обусловленность, равенство (по модулю) неизвестных между собой, наличие помех (шума), действующих на свободные члены СЛАУ. Указанный алгоритм основан на возможности построения определенной совокупности СЛАУ с существенно меньшим числом обусловленности, чем число обусловленности начальной системы, с последующей статистической обработкой решений этих СЛАУ. A mathematical model of the two-stage transportation problem is proposed to determine the optimal plan for transportation of homogeneous products from suppliers to consumers if the number of intermediate locations is bounded above. The mathematical model is formulated as a Boolean linear programming problem. The conditions under which the problem has a solution are determined, and AMPL-code for solving the problem by state-of-the-art linear integer programming solvers is given. A demo example of calculation results using gurobi program is presented. 2018 Article Алгоритм оцінювання розв’язків деяких погано обумовлених систем лінійних алгебраїчних рівнянь / В.І. Масол, Є.О. Шевченко // Компьютерная математика. — 2018. — № 2. — С. 135-144. — Бібліогр.: 6 назв. — укр. 2616-938Х http://dspace.nbuv.gov.ua/handle/123456789/161894 519.25 uk Компьютерная математика Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Теория и методы оптимизации Теория и методы оптимизации |
| spellingShingle |
Теория и методы оптимизации Теория и методы оптимизации Масол, В.І. Шевченко, Є.О. Алгоритм оцінювання розв’язків деяких погано обумовлених систем лінійних алгебраїчних рівнянь Компьютерная математика |
| description |
Пропонується алгоритм оцінювання невідомих значень системи лінійних алгебраїчних рівнянь (СЛАР), особливості якої є погана обумовленість, рівність (по модулю) між собою невідомих, наявність завад (шуму), які діють на вільні члени СЛАР. Зазначений алгоритм базується на можливості побудови певної сукупності СЛАР з суттєво меншим числом обумовленості, ніж числом обумовленості початкової системи, з подальшою статистичною обробкою розв’язків цих СЛАР. |
| format |
Article |
| author |
Масол, В.І. Шевченко, Є.О. |
| author_facet |
Масол, В.І. Шевченко, Є.О. |
| author_sort |
Масол, В.І. |
| title |
Алгоритм оцінювання розв’язків деяких погано обумовлених систем лінійних алгебраїчних рівнянь |
| title_short |
Алгоритм оцінювання розв’язків деяких погано обумовлених систем лінійних алгебраїчних рівнянь |
| title_full |
Алгоритм оцінювання розв’язків деяких погано обумовлених систем лінійних алгебраїчних рівнянь |
| title_fullStr |
Алгоритм оцінювання розв’язків деяких погано обумовлених систем лінійних алгебраїчних рівнянь |
| title_full_unstemmed |
Алгоритм оцінювання розв’язків деяких погано обумовлених систем лінійних алгебраїчних рівнянь |
| title_sort |
алгоритм оцінювання розв’язків деяких погано обумовлених систем лінійних алгебраїчних рівнянь |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2018 |
| topic_facet |
Теория и методы оптимизации |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/161894 |
| citation_txt |
Алгоритм оцінювання розв’язків деяких погано обумовлених систем лінійних алгебраїчних рівнянь / В.І. Масол, Є.О. Шевченко // Компьютерная математика. — 2018. — № 2. — С. 135-144. — Бібліогр.: 6 назв. — укр. |
| series |
Компьютерная математика |
| work_keys_str_mv |
AT masolví algoritmocínûvannârozvâzkívdeâkihpoganoobumovlenihsistemlíníjnihalgebraíčnihrívnânʹ AT ševčenkoêo algoritmocínûvannârozvâzkívdeâkihpoganoobumovlenihsistemlíníjnihalgebraíčnihrívnânʹ |
| first_indexed |
2025-07-14T14:28:45Z |
| last_indexed |
2025-07-14T14:28:45Z |
| _version_ |
1837632928159367168 |
| fulltext |
ISSN 2616-938Х. Компьютерная математика. 2018, № 2 135
Пропонується алгоритм оціню-
вання невідомих значень системи
лінійних алгебраїчних рівнянь
(СЛАР), особливості якої є погана
обумовленість, рівність (по моду-
лю) між собою невідомих, наяв-
ність завад (шуму), які діють на
вільні члени СЛАР. Зазначений
алгоритм базується на можливо-
сті побудови певної сукупності
СЛАР з суттєво меншим числом
обумовленості, ніж числом об-
умовленості початкової системи,
з подальшою статистичною об-
робкою розв’язків цих СЛАР.
В.І. Масол, Є.О. Шевченко,
2018
УДК 519.25
В.І. МАСОЛ, Є.О. ШЕВЧЕНКО
АЛГОРИТМ ОЦІНЮВАННЯ
РОЗВ'ЯЗКІВ ДЕЯКИХ
ПОГАНО ОБУМОВЛЕНИХ СИСТЕМ
ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ
Прикладні задачі, що пов’язані з аналізом
сигналів, зокрема, оцінками їх амплітуд,
приводять до необхідності розв’язувати
СЛАР, які у загальному вигляді можна
подати так:
1
1, ,
,
n
ij j i i
j
a x b
i n
(1)
де n – кількість невідомих СЛАР, і
незалежні випадкові величини, 1, ,i n
–
AWGN (адитивний білий гауссів шум). Крім
того, система (1) має такі властивості:
- визначник det(A) матриці коефіцієн-
тів А СЛАР (1) задовольняє співвідношенню
det(A) ≠ 0; (2)
- компоненти вектора розв’язку СЛАР
дорівнюють (по модулю) між собою
1 2| | | | ... | |,nx x x (3)
СЛАР (1) погано обумовлена у тому сенсі,
що визначник det(A) має значення близьке до
нуля і число обумовленості μ(A) досить
велике (системи рівнянь із зазначеними
властивостями розглядалися, зокрема, у [1]).
Велике число обумовленості характеризує
клас задач, який має назву клас некоректно
поставлених задач («inverse problems»). Як
відмічено в [6], процедура знаходження роз-
в’язків СЛАР із зазначеного класу нестійка
у тому сенсі, що при найменших збуреннях
коефіцієнтів матриці А або вектора-стовпця
'
1 2 8 , ,( , )b b b b
правої частини (1) розв’я-
зок може суттєво відрізнятися від точного.
В.І. МАСОЛ, Є.О. ШЕВЧЕНКО
ISSN 2616-938Х. Компьютерная математика. 2018, № 2136
У даній роботі пропонується алгоритм, який дозволяє оцінювати розв’язки
системи (1) шляхом побудови скінченної кількості СЛАР, які еквівалентні (1)
і з урахування властивості (3) дозволяють зменшити число обумовленості, що
врешті решт зменшує вплив шуму AWGN на значення розв’язку.
Параметр n у системі (1) обирають в залежності від роду задачі і практичної
доцільності. Так, у публікації [3] n = 8, i ≡ 0, 1,8,i матриця коефіцієнтів A
має розмір (8 x 8) і у подальшому позначатиметься як A(8 х 8) (табл. 1). Вибір
конкретних значень елементів матриці А формується відліками фільтру з харак-
теристикою типу «припіднятий косинус» (ФПК; в англомовній літературі ФПК –
Lowpass Raised Cosine FIR filter (фільтр низькочастотний «припіднятий
косинус» з кінцевою імпульсною характеристикою)), який часто зустрічається
в телекомунікаційних системах завдяки можливості мінімізувати міжсимвольні
спотворення [4].
ТАБЛИЦЯ 1. Матриця А(8x8)
h[n] A8 h[n] A7 h[n] A6 h[n] A5
57 – 0,002167 49 0,010266 41 – 0,022744 33 1
58 – 0,003514 50 0,024643 42 – 0,095621 34 0,969196
59 – 0,003461 51 0,029792 43 – 0,130815 35 0,880695
60 – 0,002659 52 0,027860 44 – 0,134201 36 0,745562
61 – 0,001658 53 0,021653 45 – 0,114696 37 0,580185
62 – 0,000809 54 0,013880 46 – 0,082303 38 0,403618
63 – 0,000260 55 0,006630 47 – 0,046308 39 0,234615
64 – 2,14E– 06 56 0,001143 48 – 0,013952 40 0,088917
25 0,088917 17 – 0,013952 9 0,001143 1 – 2,14E– 06
26 0,234615 18 – 0,046308 10 0,006630 2 – 0,000260
27 0,403618 19 – 0,082303 11 0,013880 3 – 0,000809
28 0,580185 20 – 0,114696 12 0,021653 4 – 0,001658
29 0,745562 21 – 0,134201 13 0,027860 5 – 0,002659
30 0,880695 22 – 0,130815 14 0,029792 6 – 0,003461
31 0,969196 23 – 0,095621 15 0,024643 7 – 0,003514
32 1 24 – 0,022744 16 0,010266 8 – 0,002167
АЛГОРИТМ ОЦІНЮВАННЯ РОЗВ’ЯЗКІВ ДЕЯКИХ ПОГАНО ОБУМОВЛЕНИХ СИСТЕМ ...
ISSN 2616-938Х. Компьютерная математика. 2018, № 2 137
В таблиці запис h[n] є дискретний момент часу, а запис А1 – А8 значення
імпульсного відгуку фільтра у ці моменти часу.
Імпульсний відгук фільтра (ис. 1) описується формулою [4]:
2
sin( / ) cos( / )
(t)
2
1 ( )
s s
s
t T t T
h
tt
T
і характеризується двома величинами:
- β – коефіцієнт згладжування, β є [0,1];
- Тs – тривалість символьного інтервалу в переданому цифровому сигналі,
розділяючи сусідні точки відліку на часовій осі, тобто період (крок)
дискретизації.
РИС. 1. Імпульсний відгук ФПК (T = 5, β = 0.35)
Спосіб формування правої частини СЛАР (1), тобто вихідного сигналу
з ФПК, можна подати, так як на рис. 2. А саме, на ньому схематично
представлено проходження через ФПК цифрового бінарного полярного
NRZ-сигналу (Non Return Zero), який передає цифрове повідомлення Xk ∈
(1 1 1 1 1 1 1 1). В результаті вихідний сигнал sig являє собою суму восьми
імпульсних характеристик фільтра, зміщених відносно один до одного на часові
інтервали kT і мають амплітуди Xk, рівних амплітуді відповідних вхідних
імпульсів.
Нескладно перевірити (використовуючи Matlab (наприклад, [5])), що
визначник det(A(8х8)) дорівнює det(A(8х8)) = 9,9E – 21 (отже, задовольняє спів-
відношенню (2)) і число обумовленості μ(A(8х8)):
μ(A(8х8)) = 1895428. (4)
Наслідком того, що число обумовленості μ(A(8х8)) велике, є чутливість
розв’язку навіть до невеликих збурень вектора .b
В.І. МАСОЛ, Є.О. ШЕВЧЕНКО
ISSN 2616-938Х. Компьютерная математика. 2018, № 2138
РИС. 2. Формування сигналу sig
Отримані значення для det(A(8х8)) та μ(A(8х8)) матриці A(8х8) вказують на те, що
поява у правій частині СЛАР (8 8)xA x b
, де '
1 2 8 , ,( , )x x x x
, '
1 2 8 , ,( , )b b b b
,
завад '
1 2 8 , , ),(
суттєво може змінити розв’язок системи. Наприклад, для
вектора x
:
АЛГОРИТМ ОЦІНЮВАННЯ РОЗВ’ЯЗКІВ ДЕЯКИХ ПОГАНО ОБУМОВЛЕНИХ СИСТЕМ ...
ISSN 2616-938Х. Компьютерная математика. 2018, № 2 139
' ;10;10; 10; 10( 10 ; 10; ; ,0 10)1x
(5)
який задовольняє (3), отримуємо таке значення для b
:
'( 10,841; 12,185; 12,865; 12,947; 12,577; 11,948; 11,265; 10,709)b
Водночас для завади
(0,158; 0,561; 0,857; 0,415; 0,412; 0,194; 0,265; 0,585)
(6)
розв’язком СЛАР
(8 8)xA x b
(7)
є вектор x
, який дорівнює
' 53894; 125121; 32709; 983; 921; 24136; 71540; 149( 45 ) .0x
(8)
Очевидно, значення компонент вектора (8) суттєво відрізняються від
компонент вектора (5).
Звідси випливає необхідність зменшити число обумовленості матриці A(8х8)
і тим самим отримати розв’язок, який би залишався стійким до збурень правої
частини вихідної СЛАР. У нашому випадку це можна досягти скориставшись
тим, що розв’язок має задовольняти співвідношенню (3) і , отже, компоненти
вектора розв’язку можуть відрізнятися між собою хіба що знаком. Залишилося
помітити, що кількість варіацій знаків розв’язку СЛАР (7) дорівнює 82 .
Як показано далі це дозволяє сформувати алгоритм оцінювання розв’язків СЛАР
(1) .
Алгоритм оцінювання розв'язків СЛАР (1) на прикладі оцінювання
розв'язків СЛАР (7) подамо у вигляді наступних кроків.
Крок 1. Кількість варіацій знаків розв’язку СЛАР (7) дорівнює 82 256 .
Для кожної варіації формуємо матрицю A(8х2) розмірністю 8 х 2, у якій перший
(другий) стовпець – це сума додатних (від’ємних) компонент вектора x
СЛАР
(7). Наприклад, для варіації ' ;10;10; 10; 10; 10( 10 0);10;1x
матриця A(8х8)
з коефіцієнтами, які надані в табл. 1, перетворюється у матрицю A(8х2), яка має
вигляд (табл. 2).
ТАБЛИЦЯ 2. Матриця А(8x2)
n 1 2 n 1 2
1 – 10,727974 – 0,113369 5 – 11,898889 – 0,678418
2 – 11,539898 – 0,646075 6 – 11,526890 – 0,420911
3 – 11,985500 – 0,879522 7 – 11,079310 – 0,185486
4 – 12,083927 – 0,863456 8 – 10,661705 – 0,047099
В.І. МАСОЛ, Є.О. ШЕВЧЕНКО
ISSN 2616-938Х. Компьютерная математика. 2018, № 2140
У підсумку отримуємо 256 матриць розмірністю 8 х 2. Мінімальне та мак-
симальне значення чисел обумовленості цих матриць дорівнює 29,22 та 1381,91
відповідно, що суттєво менше значення числа обумовленості (4). Числа
обумовленості матриць розраховуємо за допомогою Matlab-функції cond(A(8х2)).
Крок 2. Розв’язуємо СЛАР з матрицями коефіцієнтів отриманих на кроці 1,
а саме систем вигляду.
(8 2) ,xA y b
(9)
де '
1 2 ;( ) ,y y y
та залишаємо лише такі вектори y
, для яких виконуються
співвідношення 1 20, 0y y . Вибір зазначених розв’язків пов’язано з їх фізич-
ною інтерпретацією (амплітуда сигналу), табл. 3.
ТАБЛИЦЯ 3. Розв’язки СЛАР (7), які задовольняють умові y1 > 0 і y2 > 0
n y1 y2 n y1 y2 n y1 y2
1 11,152 2,062 8 10,035 11,341 15 9,901 3,626
2 9,926 3,877 9 10,001 11,339 16 9,985 6,049
3 9,917 3,703 10 10,147 469,441 17 9,956 6,118
4 9,992 6,382 11 9,346 470,984 18 9,959 6,515
5 9,964 6,434 12 11,212 7,918 19 9,954 6,154
6 9,983 6,548 13 11,174 7,411 20 10,023 10,818
7 9,981 6,133 14 9,912 3,775 21 9,988 10,863
У нашому випадку одночасно додатних компонент y1 та y2 виявилося 21
і всі вони належать проміжку (2,062; 470,984). Розв’язування СЛАР (7)
виконуємо за допомогою Matlab-функції linsolve ().
Крок 3. Обчислюємо статистичну характеристику отриманих на кроці 2
розв’язків, а саме, медіану m ([6]) масиву чисел, що утворений шляхом
об’єднання ( )
1 ( 1,2,...,21)y та ( )
2 ( 1,2, ..., 21)y .
Зокрема, для завади (5) маємо m = 9,955. Медіану розраховуємо за допо-
могою Matlab-функції median ().
Крок 4. Обчислюємо медіану m1 масиву чисел ( )
1 ( 1,2, ..., 21).y
Крок 5. Обчислюємо медіану m2 масиву чисел ( )
2 ( 1,2, ..., 21).y
Крок 6. Формуємо інтервал, границі якого дорівнюють interval = [min(m1,
m2); max(m1, m2)].
Крок 7. Приймаємо рішення, що розв’язок СЛАР (7) належить інтервалу
int1. У випадку завади (6) цей інтервал має вигляд [8,708; 11,04] і, очевидно,
йому належить шукане значення (див. (5)).
АЛГОРИТМ ОЦІНЮВАННЯ РОЗВ’ЯЗКІВ ДЕЯКИХ ПОГАНО ОБУМОВЛЕНИХ СИСТЕМ ...
ISSN 2616-938Х. Компьютерная математика. 2018, № 2 141
Розглянемо вплив значення параметра SNR (signal-to-noise ratio –
відношення сигнал/шум) на статистичну характеристику, що уведена на кроці 3
(медіанна) (див. табл. 4 та рис. 3).
ТАБЛИЦЯ 4. Зв’язок SNR з медіаною
n Амплі-
туда n Амплі-
туда n Амплі-
туда n Амплі-
туда n Амплі-
туда n Амплі-
туда
1 16,2764 6 12,6945 11 10,2913 16 21,2766 21 10,8471 26 9,7068
2 17,2312 7 12,0582 12 8,2551 17 8,4976 22 9,7928 27 10,2059
3 15,7945 8 9,2437 13 36,4398 18 9,8082 23 9,5423 28 9,5655
4 28,2007 9 9,9170 14 8,5817 19 12,3413 24 9,8376 29 9,9035
5 11,1377 10 12,8335 15 8,7261 20 9,8617 25 9,3042 30 10,0677
РИС. 3. Зв’язок SNR з медіаною отриманих розв’язків для 30 збурень правої частини (7)
З рис. 3 випливає, наприклад, що починаючи зі значення SNR >= 20db
медіанна m = 9,8 і, таким чином, має незначне відхилення від справжнього
значення 10 (див. (5)).
Для покращення статистичних характеристик розв’язків СЛАР пропо-
нується використовувати послідовно множину СЛАР, яка створюється на основі
використання фізичних особливостей ФПК згідно публікації [3]. Друга СЛАР
має вигляд (табл. 5). У подальшому цю множину СЛАР будемо позначати М.
В.І. МАСОЛ, Є.О. ШЕВЧЕНКО
ISSN 2616-938Х. Компьютерная математика. 2018, № 2142
ТАБЛИЦЯ 5. Матриця А(8x8)
h[n] A1 h[n] A8 h[n] A7 h[n] A6
1 – 2,14E– 06 57 – 0,002167 49 0,010266 41 – 0,022744
2 – 0,000260 58 – 0,003514 50 0,024643 42 – 0,095621
3 – 0,000809 59 – 0,003461 51 0,029792 43 – 0,130815
4 – 0,001658 60 – 0,002659 52 0,027860 44 – 0,134201
5 – 0,002659 61 – 0,001658 53 0,021653 45 – 0,114696
6 – 0,003461 62 – 0,000809 54 0,013880 46 – 0,082303
7 – 0,003514 63 – 0,000260 55 0,006630 47 – 0,046308
8 – 0,002167 64 – 2,14E– 06 56 0,001143 48 – 0,013952
33 1 25 0,088917 17 – 0,013952 9 0,001143
34 0,969196 26 0,234615 18 – 0,046308 10 0,006630
35 0,880695 27 0,403618 19 – 0,082303 11 0,013880
36 0,745562 28 0,580185 20 – 0,114696 12 0,021653
37 0,580185 29 0,745562 21 – 0,134201 13 0,027860
38 0,403618 30 0,880695 22 – 0,130815 14 0,029792
39 0,234615 31 0,969196 23 – 0,095621 15 0,024643
40 0,088917 32 1 24 – 0,022744 16 0,010266
Таким чином табл. 3 відрізняється від табл. 1 зміщенням на один стовпець
вправо, так що останній стовпець стає на місце першого стовпця. Таке
перетворення не змінює ні визначника, ні числа обумовленості отриманої
матриці. Враховуючи можливість спостереження ,b
можна отримати будь-
яку скінчену кількість систем рівнянь з метою використання для оцінювання
розв’язку системи. Наприклад, для восьми систем рівнянь ми отримуємо
наступні результати (рис. 4).
З цього рисунку випливає, що, починаючи із значення SNR >= 9db медіана
m = 9,94 має незначне відхилення від шуканого значення 10 і значення SNR
на 11 db краще ніж при використанні одній системі рівнянь.
Розглянемо часові витрати на виконання кроків алгоритму розглянутого
вище. Використано ПЕОМ з наступними апаратно-програмними характе-
ристиками:
- процесор: Intel Pentium D 3.00 GHz;
- ОЗП: 3 ГБ ;
- ОС:Windows 7;
- ПЗ: Matlab R2016b.
АЛГОРИТМ ОЦІНЮВАННЯ РОЗВ’ЯЗКІВ ДЕЯКИХ ПОГАНО ОБУМОВЛЕНИХ СИСТЕМ ...
ISSN 2616-938Х. Компьютерная математика. 2018, № 2 143
Час виконання алгоритму:
- однією СЛАР – 1 хв. 12 сек;
- вісьма СЛАР – 9 хв. 36 сек;
- вісьма СЛАР у режимі паралельного виконання обробки множин СЛАР M
(використовуючи 2 worker оператора parfor ) – 5 хв. 11 сек.
РИС. 4. Зв’язок SNR з медіаною отриманих розв’язків для 30 збурень правої частини (7)
у 8 системах рівнянь
Висновки. Всі експерименти підтвердили коректність запропонованого
алгоритму щодо приналежності значення розв’язку СЛАР побудованому
інтервалу. Запропонований алгоритм оцінювання невідомих значень СЛАР
може бути розпаралелений завдяки незалежності обчислювальних кроків його
реалізації.
В.И. Масол, Е.А. Шевченко
АЛГОРИТМ ОЦЕНИВАНИЯ РЕШЕНИЙ НЕКОТОРЫХ ПЛОХО ОБУСЛОВЛЕННЫХ
СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
Предлагается алгоритм оценивания неизвестных значений системы линейных алгебра-
ических уравнений (СЛАУ), особенности которых – плохая обусловленность, равенство
(по модулю) неизвестных между собой, наличие помех (шума), действующих на свободные
члены СЛАУ. Указанный алгоритм основан на возможности построения определенной
совокупности СЛАУ с существенно меньшим числом обусловленности, чем число обуслов-
ленности начальной системы, с последующей статистической обработкой решений этих
СЛАУ.
В.І. МАСОЛ, Є.О. ШЕВЧЕНКО
ISSN 2616-938Х. Компьютерная математика. 2018, № 2144
V.І. Masol, E.O. Shevchenko
ALGORITHM FOR ESTIMATING SOLUTIONS OF ILL-CONDITIONED SYSTEMS
OF LINEAR ALGEBRAIC EQUATIONS
An algorithm for estimating unknown values of a system of linear algebraic equations (SLAEs) is
proposed. The SLAEs have the following features: bad conditionality, equality of unknowns,
presence of interference (noise), which influence free terms of the SLAE. This algorithm is based on
the possibility of constructing a certain set of SLAEs with a significantly lower number of
conditionality than that of the initial system followed by statistical processing of solutions of these
SLAEs. Statistical processing consists in finding the median of the sample formed by a set of
solutions and constructing the interval that includes an exact solution. The influence of interference
values on the accuracy of the solutions obtained is analyzed. The examples of application of the
algorithm are presented. Noted, that parallelization can be applied in the process of estimating the
solutions of poorly conditioned SLAEs and this possibility is illustrated on the examples of
improving signal processing.
Список літератури
1. Охріменко М.Г., Жуковська О.А., Купка О.О. Методи розв’язування некоректно
поставлених задач: Навчальний посібник. К.: Центр учбової літератури, 2008. 166 с.
2. Кабанихин С.И. Обратные и некорректные задачи. Учебник для студентов высших
учебных заведений. Новосибирск: Сибирское научное издательство, 2009. 456 с.
3. ZHAO Lin jun. FPGA Implementation of Square Root Raised Cosine Pulse Shaping Filter.
Modern Electronics Technique. Jan. 2011. Vol. 34.
4. Галкин В.А. Цифровая мобильная радиосвязь. Учебное пособие для вузов. М.: Горячая
линия. Телеком, 2007. 432 с.
5. Горбаченко В.И. Вычислительная линейная алгебра с примерами на MATLAB. Учебное
пособие. СПб. 2011. 320 с.
6. Гнеденко Б.В. Курс теории вероятностей. М.: ЛЕНАНД, 2015. 448 с.
Одержано 01.11.2018
Про авторів:
Масол Володимир Іванович,
доктор фізико-математичних наук,
професор Київського національного університету імені Тараса Шевченка,
E-mail: vimasol@ukr.net
Шевченко Євген Олександрович,
аспірант Київського національного університету імені Тараса Шевченка.
E-mail: home20103010@gmail.com
|