Метод эллипсоидов для нахождения решения переопределенной СЛАУ

Описана задача минимизации выпуклой функции для нахождения Lp-решения переопределенной системы линейных уравнений при p ≥ 1 и ее частный случай при 1 ≤ p ≤ 2. Описана общая схема метода эллипсоидов и ее применение для решения выпуклых задач. Приведены результаты вычислительных экспериментов для оп...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2018
Автори:	Стецюк, П.И., Стовба, В.А., Жмуд, А.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2018
Назва видання:	Теорія оптимальних рішень
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/144980
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Метод эллипсоидов для нахождения решения переопределенной СЛАУ / П.И. Стецюк, В.А. Стовба, А.А. Жмуд // Теорія оптимальних рішень: Зб. наук. пр. — 2018. — № 17. — С. 115-123. — Бібліогр.: 8 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-144980
record_format	dspace
spelling	irk-123456789-1449802019-01-13T01:23:28Z Метод эллипсоидов для нахождения решения переопределенной СЛАУ Стецюк, П.И. Стовба, В.А. Жмуд, А.А. Описана задача минимизации выпуклой функции для нахождения Lp-решения переопределенной системы линейных уравнений при p ≥ 1 и ее частный случай при 1 ≤ p ≤ 2. Описана общая схема метода эллипсоидов и ее применение для решения выпуклых задач. Приведены результаты вычислительных экспериментов для определения параметров линейной регрессии при наличии ошибочных измерений. Описана задача мінімізації опуклої функції для знаходження Lp-розв’язку перевизначеної системи лінійних рівнянь при p ≥ 1 та її частинний випадок при 1 ≤ p ≤ 2. Описана загальна схема методу еліпсоїдів та її застосування для розв'язання опуклих задач. Наведені результати обчислювальних експериментів для визначення параметрів лінійної регресії за наявності аномальних спостережень. Described is the problem of convex function minimization for finding Lp-solution of redefined linear equations system with p ≥ 1 and its particular case with 1 ≤ p ≤ 2. Given is a general outline of ellipsoid method and its application to solving convex problems. Presented are the results of computational experiments for determination of linear regression parameters in the presence of outliers. 2018 Article Метод эллипсоидов для нахождения решения переопределенной СЛАУ / П.И. Стецюк, В.А. Стовба, А.А. Жмуд // Теорія оптимальних рішень: Зб. наук. пр. — 2018. — № 17. — С. 115-123. — Бібліогр.: 8 назв. — рос. 2616-5619 http://dspace.nbuv.gov.ua/handle/123456789/144980 519.85 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Описана задача минимизации выпуклой функции для нахождения Lp-решения переопределенной системы линейных уравнений при p ≥ 1 и ее частный случай при 1 ≤ p ≤ 2. Описана общая схема метода эллипсоидов и ее применение для решения выпуклых задач. Приведены результаты вычислительных экспериментов для определения параметров линейной регрессии при наличии ошибочных измерений.
format	Article
author	Стецюк, П.И. Стовба, В.А. Жмуд, А.А.
spellingShingle	Стецюк, П.И. Стовба, В.А. Жмуд, А.А. Метод эллипсоидов для нахождения решения переопределенной СЛАУ Теорія оптимальних рішень
author_facet	Стецюк, П.И. Стовба, В.А. Жмуд, А.А.
author_sort	Стецюк, П.И.
title	Метод эллипсоидов для нахождения решения переопределенной СЛАУ
title_short	Метод эллипсоидов для нахождения решения переопределенной СЛАУ
title_full	Метод эллипсоидов для нахождения решения переопределенной СЛАУ
title_fullStr	Метод эллипсоидов для нахождения решения переопределенной СЛАУ
title_full_unstemmed	Метод эллипсоидов для нахождения решения переопределенной СЛАУ
title_sort	метод эллипсоидов для нахождения решения переопределенной слау
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2018
url	http://dspace.nbuv.gov.ua/handle/123456789/144980
citation_txt	Метод эллипсоидов для нахождения решения переопределенной СЛАУ / П.И. Стецюк, В.А. Стовба, А.А. Жмуд // Теорія оптимальних рішень: Зб. наук. пр. — 2018. — № 17. — С. 115-123. — Бібліогр.: 8 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT stecûkpi metodéllipsoidovdlânahoždeniârešeniâpereopredelennojslau AT stovbava metodéllipsoidovdlânahoždeniârešeniâpereopredelennojslau AT žmudaa metodéllipsoidovdlânahoždeniârešeniâpereopredelennojslau
first_indexed	2025-07-10T20:36:42Z
last_indexed	2025-07-10T20:36:42Z
_version_	1837293728150061056
fulltext	ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 115 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Описана задача минимизации выпуклой функции для нахожде- ния pL -решения переопределен- ной си-стемы линейных уравнений при 1p  и ее частный случай при 1 2p  . Описана общая схема метода эллипсоидов и ее приме- нение для решения выпуклых за- дач. Приведены результаты вы- числительных экспериментов для определения параметров линейной регрессии при наличии ошибочных измерений.  П.И. Стецюк, В.А. Стовба, А.A. Жмуд, 2018 УДК 519.85 П.И. СТЕЦЮК, В.А. СТОВБА, А.A. ЖМУД МЕТОД ЭЛЛИПСОИДОВ ДЛЯ НАХОЖДЕНИЯ РЕШЕНИЯ ПЕРЕОПРЕДЕЛЕННОЙ СЛАУ Введение. Задача нахождения решения пе- реопределенной системы линейных алгебра- ических уравнений (СЛАУ) может быть све- дена к задаче минимизации выпуклой функ- ции для отыскания вектора, наилучшим об- разом удовлетворяющему всем уравнениям СЛАУ. При этом выпуклые функции могут быть как гладкими, так и негладкими. При- менение субградиентных методов миними- зации негладких выпуклых функций позво- ляет разрабатывать «универсальные» алго- ритмы для нахождения решения переопреде- ленных СЛАУ. Эти алгоритмы будут приме- нимы и для плохо обусловленных гладких выпуклых функций и, следовательно, не бу- дут зависеть от того будет ли ранг матрицы СЛАУ полным или неполным. В статье рассматривается формулировка задачи выпуклого программирования, кото- рая связана с нахождением решения пере- определенной СЛАУ, и методы ее решения на основе субградиентных методов миними- зации выпуклых функций (r-алгоритм и ме- тоды эллипсоидов). В основе оптимизацион- ной задачи стоит способ отыскания вектора неизвестных, минимизирующего pL -норму вектора невязки СЛАУ. Замечательной чертой метода эллипсоидов является то, что его скорость сходимости зависит только от размерности пространства переменных. Здесь приведено описание об- щей схемы метода эллипсоидов и обсужда- ются два его варианта – классический метод эллипсоидов Юдина – Немировского – Шора и приближенный метод эллипсоидов. П.И. СТЕЦЮК, В.А. СТОВБА, А.А. ЖМУД 116 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 1. Постановка задачи. Рассмотрим такую задачу: имеется СЛАУ: 1 или , 1,.., . n ij j i j Ax b a x b i m     (1) Здесь m nA R  – матрица, mb R и nx R – вектор правых частей и неизвестных соответственно. Задача состоит в том, чтобы найти такой вектор * n px R , кото- рый минимизирует pL -норму вектора 1= ( , , )T m my Ax b y y R   . Здесь вектор y – это вектор невязок для системы (1). Задача нахождения «наилучшей» pL -нормы вектора невязок для системы (1) соответствует задаче минимизации выпуклой функции: требуется найти 1/ * 1 argmin ( ) , n p m p p p ipx R i x f x Ax b y                  (2) где p R – скалярный параметр такой, что 1p  . Здесь 1 , n i ij j i j y a x b    1,.., ,i m а условие 1p  обеспечивает выпуклость негладкой функции ( )pf x . Задача (2) всегда имеет решение. Если m n , то система линейных уравнений является переопределенной, и если для нее ранг матрицы A равен n , то задача (2) имеет единственное решение. В общем случае решение задачи (2) не обяза- тельно будет единственным. В этом случае точка * px – одна из точек множества оптимальных решений, которому соответствует минимальное значение функции * pf в задаче (2). Хорошо известны три частные случаи наилучшей pL -нормы вектора невя- зок для системы (1). Так, при 1p  получаем 1L -норму 1 1 m i i y y   , которую еще называют «манхеттеновской»; при 2p  – евклидову 2L -норму 2 2 1 m i i y y    и, впрочем, чебышевскую L -норму 1,.., max i i m y y    – при .p   Каждому приведенному значению параметра p соответствует свой метод ре- шения задачи (2). Метод наименьших модулей (МНМ) соответствует 1,p  ме- тод наименьших квадратов (МНК) соответствует 2p  , а минимаксный (чебы- шевский) метод соответствует p  . Для решения задачи (2) можно использовать методы минимизации неглад- ких выпуклых функций. Так, например, на основе модификации r-алгоритма разработана программа linrp [1]. На основе метода эллипсоидов разработаны МЕТОД ЭЛЛИПСОИДОВ ДЛЯ НАХОЖДЕНИЯ РЕШЕНИЯ ПЕРЕОПРЕДЕЛЕННОЙ СЛАУ ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 117 алгоритмы и их программные реализации для нахождения точки минимума ( )pf x при двухсторонних ограничениях на переменные [2]. Для значений 1 2p  задачу (2) можно упростить. Этой задаче соответ- ствует задача минимизации выпуклой функции: найти * 1 1 argmin ( ) , n p m n p p ij j i x R i j x F x a x b               (3) где p R – скалярный параметр, такой что 1 2p  . Здесь ( )pF x – выпуклая функция, которая является негладкой только при 1p  . Если 1p  , то задача (3) сводится к решению задачи линейного программирования и соответствует МНМ. Если 2p  , то задача (3) состоит в минимизации квадратичной функции и соответствует МНК. При этом оптимальные значения функций в задачах (2) и (3) связаны соотношением   2 * * * * 2 2 2 2( ) ( )F x f x . Задачи вида (2) и (3) часто встречаются при обработке результатов наблю- дений, построении и анализе различного рода моделей (физических, биологиче- ских, экономических, социальных и других), при поиске компромиссных реше- ний в моделях с противоречивыми данными и т. д. Для них можно находить наилучшие параметры линейной регрессии не только с помощью классических методов МНК и МНМ, но и других методов, которым соответствуют значения параметра ,p отличные от 1p  и 2.p  2. Общая схема метода эллипсоидов. Обобщенный метод эллипсоидов [3] является алгоритмом с растяжением пространства, где коэффициент растяжения  удовлетворяет неравенству 1 2 ,n    (4) и предназначен для решения следующей задачи. Задача. На ( 2)nR n  задано векторное поле ( )g x , ( ) ng x R . Требуется найти точку x , такую, что ( ( ), ) 0g x x x  для всех nx E . Предполагается, что x существует и ( ) 0g x  для x x . Общая схема метода эллипсоидов имеет такой вид. Инициализация. Выбираем точку 0 nx R и радиус 0r такими, чтобы 1 * 0 0 0( )B x x r   , где 0B – n n -матрица. Перейдем к очередной итерации со значениями 0x , 0r , 0B . Итерационный процесс. Пусть на k -й итерации найдены n kx R , kr и n n -матрица kB . Для перехода к ( 1)k  -й итерации выполняем такие дей- ствия. П.И. СТЕЦЮК, В.А. СТОВБА, А.А. ЖМУД 118 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 Шаг 1. Вычислим ( )k kg g x . Если 0kg  , то ОСТАНОВ ( * kx x ). Шаг 2. Вычислим очередную точку 1 2 1 1 : , где 1 , 2 T k k k k k k k k k k T k k B g x x h B h r B g              . Шаг 3. Пересчитаем матрицу 1kB  и радиус 1kr   1 1 1 1 1 : 1 , : 2 T k k k k k k kB B B r r                      . Шаг 4. Переходим к ( 1)k  -й итерации с 1kx  , 1kr  и 1kB  . Теорема. Генерируемая обобщенным методом эллипсоидов последователь- ность точек   0k k x   удовлетворяет неравенствам ( ) , 0,1,2,k k kA x x r k   , (5) где 1 k kA B . Если  удовлетворяет неравенству (4), то отношение объемов эл- липсоидов  : ( )k k k kE x A x x r   и  1 1 1 1: ( )k k k kE x A x x r      , локализу- ющих точку x , есть величина постоянная и равна 1( ) 1 1 1 ( ) 1, 0,1,2, ( ) 2 n k n k vol E q k vol E                  (6) В теореме соотношения (5) и (6) означают, что метод эллипсоидов сходится (по объему локализации точки x ) со скоростью геометрической прогрессии со знаменателем ( ) 1nq   . Величина знаменателя зависит от выбранного значения  , удовлетворяющего неравенству (4). Наименьший знаменатель прогрессии реализуется в методе эллипсоидов Юдина – Немировского – Шора [4, 5]. Ему соответствует коэффициент растяжения 1 1 1 n n     и достигается он в точ- ке минимума функции ( )nq  по  . Близкий к наименьшему знаменатель про- грессии реализуется в приближенном методе эллипсоидов [6], и ему соответ- ствует коэффициент растяжения 2 2 1 1 1 n n     . Он достигается в точке ми- нимума функции ( )nQ  , которая аппроксимирует сверху функцию ( )nq  со- гласно следующему соотношению: 1 1 1 1 1 1 1 1 ( ) 1 2 exp 2 ( ). 2 2 2 n n n n n q Q                                               МЕТОД ЭЛЛИПСОИДОВ ДЛЯ НАХОЖДЕНИЯ РЕШЕНИЯ ПЕРЕОПРЕДЕЛЕННОЙ СЛАУ ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 119 При больших значениях n знаменатели геометрической прогрессии в обоих методах аппроксимируются сверху близкими величинами 1( ) 1 2 q n n   и * 2 1 1( ) 1 2 2 Q n n n    . 3. Выпуклые задачи и метод эллипсоидов. Далее приведем описание двух выпуклых задач, для решения которых можно использовать метод эллипсоидов. 1. Задача безусловной минимизации выпуклой функции. Пусть ( )f x – вы- пуклая функция, где nx R . Ее минимальное значение будем обозначать * = ( )f f x и, не ограничивая общности, будем предполагать, что точка x – единственная точка минимума. Пусть имеется априорная информация, что точка x находится в шape  0 0( , ) :nS x r x R x x r    . Тогда для векторного поля ( ) ( )fg x g x , где ( )fg x – субградиент функции ( )f x в точке ,x выполняется неравенство     * * , ( ) , ( ) ( ) ( ) ( ) 0, .n fx x g x x x g x f x f x f x f x R          (7) Следовательно, для нахождения точки x можно использовать метод эллип- соидов, установив стартовую точку 0x , начальный радиус 0r r и матрицу 0 nB I , где nI – единичная n n -матрица. В качестве критерия останова можно использовать условие ( )T k k f kr B g x   , которое при сколь угодно малом  поз- воляет найти точку * kx x  , для которой * ( )f x f    . Это следует из того, что справедливо неравенство * 1 * 1 * ( ) ( , ( )) ( ) ( ) ( ), , ( ) ( ) ( ) T k f k k f k k k k k k k T T T k f k k f k k f k B g x x x g x f x f r B x x B x x B g x B g x B g x                  которое имеет место для выпуклой функции ( )f x с учетом неравенства (7). 2. Общая задача выпуклого программирования. Найти * * 0 0 0( ) min ( ) nx R f f x f x    (8) при ограничениях ( ) 0, 1,2, , ,if x i m  (9) где ( )if x – выпуклые функции, определенные на nR , ( )ig x – соответствующие субградиенты, 0,1, ,i m . Пусть известно, что оптимальная точка x суще- ствует и находится в шape 0( , )S x r (формально к системе ограничений (9) мож- но добавить ограничение 0x x r  ), и для задачи (8), (9) выполнено условие Слейтера. Рассмотрим векторное поле ( ),g x построенное следующим образом: П.И. СТЕЦЮК, В.А. СТОВБА, А.А. ЖМУД 120 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 0 1 * 1 ( ), если max ( ) 0, ( ) ( ), если max ( ) ( ) 0. i i m i i i i m g x f x g x g x f x f x          (10) Покажем, что ( ( ), ) 0g x x x  при всех nx R . Если 1 max ( ) 0i i m f x    , то 0( ) ( ),g x g x и соответсвенно имеем * * 0 0 0( ( ), ) ( ( ), ) ( ) ( ) 0.g x x x g x x x f x f x      (11) Если 1 max ( ) 0,i i m f x    то ( ) ( )ig x g x , причем ( ) 0if x  , * ( ) 0if x  , тогда имеем * * * * ( ( ), ) ( ( ), ) ( ) ( ) 0i i ig x x x g x x x f x f x      . (12) Таким образом из (11), (12) следует справедливость неравенства ( ( ), ) 0g x x x  при всех nx R . Следовательно, вычисляя ( )g x по формуле (10), для локализации оптималь- ной точки x в задаче (8), (9) можно использовать обобщенный метод эллипсо- идов. Отметим, что этот результат не изменится, если во второй формуле (10) вместо ( )ig x взять , i g где i – произвольный индекс, для которого ( ) 0 i f x  . Останов по условию 0 ( )T k k kr B g x   позволяет найти точку * kx x  , для кото- рой * * 0 0( )f x f    , что следует из справедливости неравенства * * 1 * 1 * 0 0 0 0 0 0 0 ( ) ( , ( )) ( ) ( ) ( ), ( ) ( ) ( ) T k k k k k k k k k k T T T k k k k k k B g x x x g x f x f r B x x B x x B g x B g x B g x                  для выпуклой функции 0 ( )f x . Останов по условию 0 ( )T k k kr B g x   использует- ся в программной реализации алгоритма на основе классического метода эллип- соидов Юдина – Немировского – Шора [2]. 4. Ошибочные измерения и МНМ. Рассмотрим пример задачи определе- ния параметров линейной регрессии [7, с. 10] для функции одной переменной. Результаты наблюдений  , ,i ix y среди которых имеется одно ошибочное изме- рение (5,0), показаны на рис. 1. Их требуется аппроксимировать линейной функцией ,y cx d  где c и d – неизвестные. РИС. 1. Результаты наблюдений [7, с. 10] для функции одной переменной МЕТОД ЭЛЛИПСОИДОВ ДЛЯ НАХОЖДЕНИЯ РЕШЕНИЯ ПЕРЕОПРЕДЕЛЕННОЙ СЛАУ ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 121 В работе [7] показано, что метод наименьших модулей является более пред- почтительным, поскольку игнорирует ошибочное измерение (5,0) и точно восстанавливает линейную функцию .y x Задачу определения наилучших параметров линейной функции y cx d  можно сформулировать как задачу вида (2). Она будет иметь такой вид: найти 1/ * * , 1 2 2 ( , ) argmin ( , ) . 3 3 4 4 5 p p p p p p p p p pc d d c d c d c d f c d c d c d c d                          (13) Для различных значений 1 2p  результаты решения задачи (13) с помо- щью алгоритма на основе метода эллипсоидов [2] приведены в табл. 1. Значе- нию параметра 1p  соответствует МНМ, а значению 2p  – МНК. ТАБЛИЦА 1. Результаты решения задачи (13) алгоритмом [2] при различных p p itn * pc * pd * ( , )p p pf c d 1 200 1.0000 3.4408e-012 5.0000 1.05 174 0.99990 3.5115e-005 4.9999 1.1 138 0.99065 9.3409e-003 4.9965 1.2 119 0.86343 1.3768e-001 4.9047 1.3 111 0.70080 3.1609e-001 4.6989 1.4 107 0.57606 4.7512e-001 4.4615 2 104 0.28571 9.5238e-001 3.4503 Здесь параметр p пробегает значения от 1 до 1.4 с шагом 0.1 и с шагом 0.05 от 1 до 1.1; itn – количество итераций, затраченных на нахождение оптималь- ных параметров pc и * pd с точностью * * * * 12( , ) ( , ) 10p p p p p pf c d f c d   . Использова- лись: стартовая точка (0,0) и радиус локализации 3r  . Из табл. 1 видно, что при 1p  измерение (5,0) игнорируется и получаем линейную функцию ,y x при очень близких к единице значениях параметра p влияние ошибочного из- мерения мало чувствуется, но при 1.3p  и 1.4p  его влияние очень сильное (графически это показано на рис. 2). РИС. 2. Наилучшие линейные функции * * p py c x d  при [1;1.3;1.4; 2]p П.И. СТЕЦЮК, В.А. СТОВБА, А.А. ЖМУД 122 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 Следовательно, использование алгоритма на основе метода эллипсоидов [2] в каждом конкретном случае позволяет подбирать параметр p так, чтобы от- брасывать или оставлять «ошибочные» измерения в случае их состоятельности. Рассмотрим пример аппроксимации результатов наблюдений из анкеты опроса [2]. Имеется 28 векторных наблюдений  ,i iu f , 4 iu R , if R , которые необходимо «наилучшим образом» приблизить квадратичной функцией вида ( ) T TQ u u Au b u c   , где 4u R , A – симметрическая 4 4 -матрица, 4b R , c R . Эта задача сводится к оптимизационной задаче (3) от 15 переменных. При этом значению параметра 1p  соответствует МНМ, а значению 2p  – МНК. Сравнение результатов работы МНМ и МНК приведено в табл. 2. ТАБЛИЦА 2. Сравнение МНМ и МНК для наилучших квадратических функций i T iu if 1 iQ 1 i if Q 2 iQ 2 i if Q 3 (1.5, 8.5, 2.5, 5.2) 0.5 0.501 -0.001 0.506 -0.006 4 (1.5, 8.5, 2.5, 5.2) 0.5 0.501 -0.001 0.506 -0.006 7 (2.0, 8.5, 2.0, 5.2) 0.5 0.501 -0.001 0.505 -0.005 13 (4.0, 7.9, 5.4, 8.6) 0.9 0.896 0.004 0.881 0.019 20 (5.9, 7.7, 4.7, 6.4) 1.0 0.995 0.005 0.988 0.012 22 (2.0, 9.0, 2.2, 7.0) 0.9 0.897 0.003 0.886 0.014 24 (1.1, 9.0, 3.1, 7.0) 0.9 0.895 0.005 0.878 0.022 25 (1.1, 9.0, 2.2, 7.9) 0.9 0.899 0.001 0.889 0.011 26 (2.0, 8.1, 3.1, 7.9) 0.9 0.974 -0.074 0.918 -0.018 27 (2.0, 8.1, 3.1, 7.9) 0.9 0.974 -0.074 0.918 -0.018 Здесь второй и третий столбцы содержат наблюдения, четвертый и шестой – значения функций, полученных с помощью МНМ и МНК. Пятый и седьмой столбцы отражают отклонения заданных значений (третий столбец) от значений полученных с помощью аппроксимирующих функций. В таблице представлены лишь те наблюдения, для которых отклонение в пятом столбце не равно нулю. Из табл. 2 видно, что если наблюдения 26 и 27 не учитывать, то использование МНМ предпочтительнее, чем МНК. Выводы. Метод элипсоидов можно успешно применять для нахождения приближений к решению переопределенной СЛАУ при небольшом количестве переменных в задачах (3) и (4). Чтобы при 10n  найти приближение к реше- нию с относительной точностью по значению функции, равной 1010 , методу эллипсоидов Юдина – Немировского – Шора достаточно осуществить 4600 ите- раций. При 1000m  для современных персональных компьютеров это требует меньше секунды процессорного времени. Поэтому с помощью метода эллипсо- идов задачи нахождения приближений переопределенной СЛАУ при 10n  и 1000m  можно решать в реальном времени на современных компьютерах. При этом алгоритмы будут устойчивыми при решении плохо обусловленных СЛАУ. МЕТОД ЭЛЛИПСОИДОВ ДЛЯ НАХОЖДЕНИЯ РЕШЕНИЯ ПЕРЕОПРЕДЕЛЕННОЙ СЛАУ ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 123 Работа выполнена при поддержке НАН Украины, проекты № 0117U000327 и № 0116U004558. П.І. Стецюк, В.О. Стовба, О.О. Жмуд МЕТОД ЕЛІПСОЇДІВ ДЛЯ ЗНАХОДЖЕННЯ РОЗВ'ЯЗКУ ПЕРЕВИЗНАЧЕНОЇ СЛАР Описана задача мінімізації опуклої функції для знаходження pL -розв’язку перевизначеної системи лінійних рівнянь при 1p  та її частинний випадок при 1 2p  . Описана загальна схема методу еліпсоїдів та її застосування для розв'язання опуклих задач. Наведені результати обчислювальних експериментів для визначення параметрів лінійної регресії за наявності аномальних спостережень. P.І. Stetsyuk, V.A. Stovba, A.A. Zhmud ELLIPSOID METHOD FOR FINDING SOLUTION OF LINEAR EQUATIONS SYSTEM Described is the problem of convex function minimization for finding pL -solution of redefined linear equations system with 1p  and its particular case with 1 2p  . Given is a general outline of ellipsoid method and its application to solving convex problems. Presented are the results of computational experiments for determination of linear regression parameters in the presence of outliers. Список литературы 1. Стецюк П.И., Колесник Ю.С. К вопросу выбора метода аппроксимации результатов измерения. Интеллектуальные информационно-аналитические системы и комплексы. Киев: Ин-т кибернетики имени В.М. Глушкова НАН Украины, 2000. С. 62 – 67. 2. Стецюк П.И., Стовба В.А., Мартынюк И.С. Алгоритм метода эллипсоидов для нахож- дения Lp-решения системы линейных уравнений. Теорія оптимальних рішень. Київ: Інститут кібернетики імені В.М. Глушкова НАН України. 2017. С. 139 – 146. 3. Стецюк П.И. Общая схема метода эллипсоидов. Информационный бюллетень АМП № 13. Екатеринбург: УрО РАН, 2015. С. 59 – 60. 4. Юдин Д.Б., Немировский А.С. Информационная сложность и эффективные методы решения выпуклых экстремальных задач. Экономика и математические методы. 1976. Вып. 2. C. 357 – 369. 5. Шор Н.З. Метод отсечения с растяжением пространства для решения задач выпуклого программирования. Кибернетика. 1977. № 1. С. 94 – 95. 6. Стецюк П.И. Приближенный метод эллипсоидов. Кибернетика и системный анализ. 2003. № 3. С. 141 – 146. 7. Кларк Ф. Оптимизация и негладкий анализ. М.: Наука, 1988. 280 с. 8. Стецюк П.И., Колесник Ю.С., Лейбович М.М. О робастности метода наименьших моду- лей. Компьютерная математика. 2002. С. 114 – 123. Получено 18.04.2018

Метод эллипсоидов для нахождения решения переопределенной СЛАУ

Репозитарії

Схожі ресурси