автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Алгоритмы метода полных наименьших квадратов и их применение в задачах идентификации динамических систем

РГБ ОД 3 О МАЙ 2300

На правах рукописи

Шамаров Павел Александрович

АЛГОРИТМЫ МЕТОДА ПОЛНЫХ НАИМЕНЬШИХ КВАДРАТОВ И ИХ ПРИМЕНЕНИЕ В ЗАДАЧАХ ИДЕНТИФИКАЦИИ ДИНАМИЧЕСКИХ СИСТЕМ

1еднальностт>: 05.13.16- применение вычислительной техники, математического моде-тропанил и математических методов в научных исследованиях.

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Самара-2000

Работа выполнена в Самарском государственном аэрокосмическом университете имени академика С.П. Королева

Научный руководитель

доктор физико-математических наук, профессор Л.И. Жданов.

Официальные оппоненты

доктор физико-математических наук, профессор В.II. Радчеико, доктор технических наук, доцент В.А. Фурсов.

Ведущая организация

Самарский государственный университет

Защита состоится "......" июня 2000 г. в......часов на заседании

диссертационного совета Д 063.87.02 при Самарском государственном аэрокосмическом университете имени академика С.П. Королева по адресу 443086, г. Самара, Московское шоссе, 34.

С диссертацией можно ознакомиться в библиотеке Самарского государственного аэрокосмического университета, имени академика С.П. Королева.

Автореферат разослан

Ученый секретарь диссертационного совета д.т.н., доцент

8оз

Общая характеристика работы

Актуальность темы. Задача отыскания эффективных способов решена систем линейных алгебраических уравнений (СЛЛУ) в ее различных остановках является, по-видимому, в историческом плане одной из древ-ейших проблем в математике. Наличие неизбежных погрешностей (возмущений) и задании коэффициентов как в правой, так и в левой (матрице) ее астях, порожденных либо неточностью самих исходных данных в той со-ержательной задаче, математической моделью которой является рассматриваемая система уравнений, либо конечной точностью представления исел в ЭВМ, либо и тем и другим вместе, приводит к неопределенности скомого решения. Известно, что классические алгоритмы решения СЛАУ, снованные па концепции абсолютной точности, при наличии погрешно-гой не могут быть положены в основу универсальных вычислительных рограмм для ЭВМ в силу неустойчивости решений к погрешностям.

Проблема нахождения решений приближенных (как детерминирован-ых. так и стохастических) СЛАУ возникает в огромном числе задач маема п4чеекого моделирования. К их числу принадлежат задачи регресси-нного анализа с ошибками в независимых переменных, идентификации тохастмческих дискретных динамических систем, описываемых линейны-1И разностными уравнениями, восстановления сигналов и многие другие. I настоящее нремя наиболее разработанной является задача решения прилаженных СЛАУ, в которых неточно задан лишь вектор правой части, а [атрица системы задана точно. Одним из наиболее эффективных и уни-ерсальных методов решения этой задачи является классический линей-ый метод наименьших квадратов (МНК). Это связано с тем фактом, что настоящее время имеется достаточное число высоко эффективных в вы-исли'гсльном отношении алгоритмов для МНК, а также, что многие ста-мстипескпе свойства оценок решений, полученных на основе МНК для риб.тижеииых стохастических СЛАУ (задач регрессионного анализа), не авигят от фушецпй распределений возмущений.

'Значительно менее разработанными являются методы решения прибли-сенных СЛАУ (как детерминированных, так и стохастических), когда не-очио заданы как вектор правой части, так и матрица коэффициентов 71А У. Одним из методов решения таких задач является метод полных аименьших квадратов (МГШК), который является естественным обобще-нем МНК на случай приближенных СЛАУ с неточно заданной матрицей о'х{)фии.иситов.

Постановка задачи полных наименьших квадратов впервые была рас.-уютреиа академиком Ю.В. Лишшком (под названием "метод ортогональ-ых проекций") применительно к задачам регрессионного анализа. В даль-

нейшем, значительный вклад в развитие МШГК и его анализ внесли Л.Л: Жданов, A.B. Крянев, а также зарубежные ученые Д. Голуб (G. Golub С. Ван Лоан (С. Van Loan), С. Ван Хаффел (S. Van HufFel), Д. Вандевей, (J. Vandewalle), А. Бьорк (Â. Björk).

Для стохастических задач МПНК сохраняет большинство свойств клас сического линейного МНК, таких, например, как независимость от ко), кретного вида функций распределения ошибок. По вычислительная задач полных наименьших квадратов (ПНК) значительно сложнее, чем задач линейных наименьших квадратов. Задача ПНК является нелинейной и большинстве случаев плохо обусловленной. Плохая обусловленность и ада чи не позволяет эффективно применять численно устойчивые алгоритм] без значительного увеличения числа арифметических операций, необходг мых для ее решения.

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

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

Для достижения поставленной в работе цели были решены следу ющи задачи:

1. Преобразование исходной задачи. 11Г1К к задаче решения совместно, расширенной СЛАУ.

2. Исследование обусловленности расширенной СЛАУ, соответствую щей задаче ПНК.

3. Разработка численного алгоритма для решения расширенной CJIAi соответствующей задаче ПНК большой размерности.

4. Исследование и выбор алгоритма для вычисления минимального спи гулярного числа в задаче ПНК.

5. Решение на основе ПНК частично приближенных СЛАУ (вектор пра вой части и некоторая часть столбцов матрицы этих С'ЛЛУ известны при ближенно) в задачах параметрической идентификации дискретных лере даточных функций.

6. Проведение на ЭВМ тестовых исследований разработанных алгорит мов.

Научная новизна заключается в следующем:

• Исходная задача ПНК преобразована к задаче решения cobmccthoi

расширепной СЛАУ.

• Предложена модификация расширенной СЛАУ, соответствующей ИНК, с масштабным множителем, позволяющим снизить число обусловленности исходной задачи.

• Разработан специальный вариант прямого проекционного метода для решения расширенной СЛАУ соответствующей ПНК, который позволяет существенно сократить число арифметических операций, требуемых для ее решения.

• Найдены экспериментальные оценки для оптимального масштабного множителя.

• (! помощью обратного анализа, ошибок проведено доказательство устойчивости данного подхода с применением оптимального масштабного множителя к расширенной СЛАУ.

• Вычислено значение оптимального множителя в зависимости от нормы искомого вектора.

• Разработай численный алгоритм идентификации параметров дискретных передаточных функций линейных динамических моделей.

Научная и практическая ценность работы определяется эффектив-юстыо разработанного численного метода с точки зрения точности полу-темых решений и арифметической сложности их вычисления. Предлагает й численный метод предназначен для решения задачи ПНК, которая ■озннкает и численном анализе, регрессионном анализе, а также в прикладных задачах восстановления сигналов, параметрической идентифи-:ацни и многих других. Подробное исследование обусловленности разра-¡отатшых алгоритмов позволило математически обосновать их численную етойчивость. Особо следует подчеркнуть возможность применения раз->абот;ншых алгоритмов на векторных компьютерах, в связи с растущим шторос.ом в мире к параллельным вычислениям.

Методы исследований. При формулировке и доказательстве результатов используются положения линейной алгебры, теории вероятностей, сорип возмущений, а также теории идентификации дискретных динами-юских систем. Исследования полученных методов и алгоритмов проводи-нтсь па основе имитационного моделирования. При разработке программ-юго обеспечения использовался пакет МАТЬ А В (версия 5.3).

Автором опубликовано по теме диссертации 4 печатных работы, спи-ок которых приведен и конце автореферата.

Структура и объем работы. Диссертация состоит из введения, трех лап. заключения и списка литературы из 84 наименований источников п-ечествешюй и зарубежной литературы. Объем диссертационной работы 08 страниц.

Основные положения, выносимые на защиту.

• Новый вычислительный алгоритм решения задачи полных liai меньших квадратов.

• Решение задачи преобразования исходной системы, к ^расширенно

' 'СЛАУ.'"."!';:"'"■"''' .........................

« '1 "V ' Исследование числёнйоЙ обусловленности расширенной СЛАУ, ее '■■101 ответствующей задаче ПГ1 К.

<!' Выбор: onTHMÏJÎiiiàfd'Масштабного ;кпо>кйтеля -'Для сиижеиия ' об

1 условлёяности задачи ПНК. 1Г; Исследование ' устойчивости'1 разработанного' Алгоритма' мйо^о

; ' : 'обратного анализа ошибок .ir;î * • ' r : ! : : ■ i ' ' ." ..........1

■ > ^Новый вычиЙлиТёЖный клгоритМ решения задачк'идентис^нка'ци - параметрбв'-ййскрёгнь'й передаточной функции.

Результаты ТёстйрЬйаНИ! 'й^имитййиоиных''численныхйсследовс ....и-...-.ний; ---> ;! 'i'О' :■.:.•.■. -

Краткое содержание работы

В введении обоснована актуальность темы исследования, дана обща характеристика работы, определены цель и задачи исследований, цршк дены структура и краткое содержание диссертационной работы, оснонны положения, выносимые на защиту.

В главе 1 рассматривается общая постановка задачи полных наймет ших квадратов и дается обзор известных численных методов ее решении Рассматривается приближенная (в общем случае переопределенная СЛАУ вида

• |!схо\тцэм эиЧУ до ПНК iibwftMïk&sm» к з*№м</ Ьсшыш» coir/iu..ur

С ешы Р/ ' / > г»Г ranfeC = Р, d е к ■', (

доЪ<ш»а НОШ131Ш я^к-Лолзсхся r> eueiiAionrt;vi:

яиглучае, когдаошибк>£ ДС и Дс! содержатся как и правой части d = </'+Д( •цта^ЙИА зн^нша^J9THX величин.

ней -

пои »госал н l'GKoiobau «rac.xr cio'v.pn'pn w-jj.iirinpi ,-шг/ С,':Г/'А нзмххии ul'i

;г ¡-_,с1П0К1к; н$г осиош Ш11С «л^Жо ОД^шжсишчх (^»'-к.ьоЬ п? ^

среди всех матриц ГЕ, г) таких,, что система ,,

V и В]>к/оЬ ^тюЬпхяя'и» т.шскшня уишали-пмготи.

С001В61СшЪсшГек ззизцв гип(©о{11Й1)р1Ч=Ьй.г^!г]-н.(ос,11г (3

имеет единственное решение. Здесь || ■ Ц^ - фробепиусова (евклидова) м? тричная норма. Вектор шшс. являющийся решением уравнения (3), д.п

1С. /■), удовлетворяющих (2), называется решением приближенной СЛАУ 1) )! смысле полпых наименьших квадратов.

Нахождение такого решения эквивалентно определению правого син-•улярного лектора расширенной матрицы (С, с/), соответствующего миии-[альпому сингулярному числу. Последняя задача, в свою очередь, свои! те я к решению алгебраической проблемы собственных значений, кото->ая как известно имеет ряд существенных недостатков вычислительного характера. Эти недостатки хорошо видны на примере проведенного в дис-:ер'пш.!ш анализа численных алгоритмов на основе отношения Рэлея и ньютоновских подходах нахождения собственных векторов матриц.

Альтернативным подходом к решению задачи Г1НК является ее сведете к нелинейной скалярной проблеме поиска минимального сингулярного тела <г матрицы (С, (I) и решения СЛАУ

(СТС - а2[)у = Ст<1, (4)

называемой смещенной нормальной системой. Здесь I - единичная матри-1а. (4) предполагается, что сг < сгт,п(С), где <тт\п{С) - минимальное •ингулярное число матрицы С. Такое условие является необходимым и юстаточпым для существования и единственности решения задачи полных наименьших квадратов.

Однако система (4) часто оказывается плохо обусловленной, так как Фи (^пшДО - 0-2) 0

сонсКС'гС-сгЧ) = - оо.

Гак им образом, подход, основанный на формировании смещенной нор-иалыюИ системы (4), приводит к снижению точности решения задачи "ШК.

Глава 2 посвящена разработке специального варианта прямого проек-шонного метода для решения задачи полпых наименьших квадратов и юдробному исследованию его вычислительных свойств, Для того, чтобы гзбежать формирования смещенной нормальной системы (4), в диссертант предлагается преобразовать задачу ПНК к расширенной СЛАУ вида

/ и Оир С \ ( г \ ( Ас = 6 о 0„Х1 1р ]<т1р г„ = 0Р , / = -1. (5) V С'г ЗО.!,, Орхр / \ у ) \ Ор }

Эдп.чко преобразование задачи ПНК к расширенной СЛАУ (5) приводит к .•величеиию размерности исходной задачи. Поэтому решение системы (5)

известными методами при большой размерности исходной задачи сопря жено с трудностями вычислительного характера. Для решении СЛАУ (5 в диссертации разработан специальный вариант прямого проекционное метода

Р. = r,W

Pi + l

Xi + l

Pi

2(i) aT

Pi

= x¡ -f

w.+l

bi+i

1

~zi+1

Pz = L,

Xo - o,

(6

J, V, 6 a", wi+i = aJ+L -4i\, i = o, 1,..., n

a i - i- й столбец матрицы А. Учитывая специальную структуру матриц! СЛАУ (5) и векторов алгоритма (6)-(7), в диссертационной работе док азы вается, что можно решить первые т — l+р уравнений расширенной систе мы аналитически. Это означает, что удается заранее вычислить значени: векторов, используемых в итерационном процессе до пг-го шага включи тельно, а также указать структуру векторов, получающихся на последу гощих шагах алгоритма. Для вывода алгоритма прямого проекциоппог метода, предназначенного для решения расширенной системы (5), требу готся следующие вспомогательные результаты, которые1 были получены диссертации. . - . ..

Лемма 1. Пусть [zs*+1^]k - обозначает k-ю координату вектора тогда VI = 0, J, ..., р — 1 и Nk — 1,2,...,р справедливо следующее утвер ждение

-ja[z^]l+k = Hm+í)]¡+P+t, Vi = т + t + 1,. .., н. Следствие. Матрицы Pm+t

и векторы xrn^t итерационного процесс*

имеют следующую структуру:

/ F

—jff D -3<Tlp~t D

-Pm+t —

О

n x(m+í)

\

\

i,

П

Im+i = I -ja-yt

\ y¡

p-t

/

где F, D - некоторые подматрицы, получающиеся в результате дейстии алгоритма (6), и

Рт = оп>

~С '-3<?1р 4

Из леммы 1 и ее следствия видно, что решение системы (5) сводится к ¡ешепию р уравнении, равному числу неизвестных переменных. А в итерационном процессе (С)-(7) можно снизить размерность используемых век-оров с )?! + р до т и избежать использования арифметических операций комплексными числами.

Предложенный в диссертации алгоритм определяется следующей тео-

1СМ0И.

Георома 1. Пусть е)ля матрицы А выполняются условия

( "и

\ «¿1

• аи \

ск>1 | ..... /0 «=1,2,..,,т + р (8)

аи )

векторы £ К', € Жр, г, 6 К', ¿/г- £ удовлетворяют следу-

ющей системе рекуррентных уравнений

■Т,, ( ,„(»') \

. (9)

де г,+1 = + (Л г = 0,1,...,р-2, У = 2,...,р, <р[й) = -сь

= е^, к — 1,. .., р; Ск, е> - к-с столбцы матриц С и I соответственно;

+ : \ = ( П\_с]±1п[ ^ _ (10)

т+1 / V ) п+1 \ т,-?1 /

де /' = 0, 1, ..., р — 1. го = с1, 1/о = 0.

Тогда условия (8) являются необходимыми и достаточными для того, ни о бы

Тг + 1 Ф О, V» =0, 1.....р- 1.

1ри этом цр будет, решением СЛАУ (4), то есть

Ур = (СТС-ег21Г1СТе1.

Для исследования погрешности решения расширенной системы (5) необ-:одимо определить спектральное число обусловленности сопёг А. Решение оследпсй задачи значительно затрудняется тем, что матрица А не явля-тся нормальной, (т.е. А* А ф'АА*). В диссертации показано, что сопсЬ-А южно выразить как функцию от минимального и максимального сингу-[ярных чисел матрицы С. Зависимость сопс^ А от о-т;11(С), <гтах(С) опре-.еляется следующей теоремой

Теорема 2. Пусть собственные числа i — 1,..., I матрицы СО1 упс рядочены следующем образол4,:

" > ■ • ■ > /V' /1рт1 = • • ■ = 0.

Тогда матрица А системы (5) имеет ■четыре группы сингулярных чисг сг^). /г = 0, ... ,3 соответственно равных

^ = 1,

- 2

i V3

(2) _ 2

i v/3

(3) _ 2

i ^

i ~ 1,..

1

ЗаД (|(¿ -

F vTÍ^T^. cos [-arceos ^ 2 (1 + ^ + ^„y

/Г",-¡-2 í X 1 I (A'i-C2)

f0 + „ + . cos ( _ _ _аксм

/Г--;—J I 71 , 1 í 3V3 (/'¿ - °"2)

? 0 + w + СГ2 . сое | - + - arceos I — ^ + ^

Приятом сингулярные числа матрицы А удовлетворяют соотношет

ям

V?: = i.....р, Vs = i.....i-p.

и crmax(A) = amin(A) = 43).

Анализ свойств числа обусловленности расширенной матрицы А пок< зывает, что при некоторых условиях прямое ее формирование может i улучшить обусловленность задачи по сравнению с (4). В диссертации ripe, ложено расширенную систему (5) преобразовать к системе

/ I, 0Ыр кС \ ( кг \ / kd \ А(к)х = Ъ о Opx¡ 1р jkcrlp кга = 0,, , \ кСТ jkcrlp ОрХр } \ у } \ 0Р /

где к - некоторый масштабный множитель, влияющий на число o6yc.ni вленности А. В диссертационной работе решается задача поиска

¿opt = Argmij) {condj .4(¿)}.

- н~

СО!)(1-Л< X J

V.

36

> зо

25 20 1Ъ 10

. t

" Г 5 10 15

Рис.]. Пример, зависимости1'числа обусловленности матрицы А ох множителя к

^ложный вид зависимости

coiidi) А(к)

i/J + k2^„,ia + k-'cr-

I a,-ccos f 3VS-Л \

J + i arcc™ ( -ta(*mm-°,3>

с позволяет найти аналитическое выражение для к0pt. Вычислить kopt южно только используя численные методы нахождения минимума не-пнейных скалярных функций. В диссертационной работе предлагается юрмула для оценки оптимального множителя

:(<тга1п(С) + а)у + т

'акая оценка, как показывают вычислительные эксперименты, является остато'шо близкой к i;optr ^ v ~ с 'и)

Число обусловленности матрицы А оценивает верхнюю границу возра-Щ»№ у)г ■ Но также важно

иендач lio^feU ^сомяянеЩ!вектораивиотделыюйти^.что

ультатм получены с помощью обратного анализа ошибок округления

¡г/ - ф. ) - "маш1:,+2p<w(G) I a-\(G)f(k)

где

G =

2Р - константа, зависящая только от размерности задачи, и гМ(Ш, машинный эпсилон (машинная точность). Обусловленность самой задач ПН К будет характеризоваться отношением

«пнк(^) =

Поэтому при решении проблемы

кпнк(^) — min

достаточно рассмотреть задачу минимизации функции f(k) но параметр к. В работе показывается, что минимум достигается на

,„ _f II3/II2 \1/2 ( 1 1ЫЬч1/3

Vopt Umin(G)||r||2// \\rhj ■

Минимальное значение Jm\n при этом будет равно

/min = (1 + -яг 1 (ГЛ |]у||2 = (1 + ^pt0-mill(r/))2cr-;n(r/)||r||L,

В диссертации показывается обратная устойчивость алгоритма " в случае применения оптимального множителя A|pt. Также доказываете: что при использовании в качестве масштабного множителя

к*"

не зависимо от норм решения Ц2/Ц2 и невязки ЦгЦо, сон сЬ А(к**) имеет тс же порядок, что и сопс^ А(коР1), и свойство обратной устойчивости алг ритма сохраняется.

В главе '2 также приводятся результаты имитационных исследонаш вычислительных свойств разработанного метода и сравнительный анад1 с методами Холецкого и отношения Рэлея. Полученные эксперимеитал ные данные позволяют сделать вывод об эффективности разработан и ь алгоритмов на классе плохо обусловленных задач большой размерностг

е(0

(О-

В(дл) А(д-)

х(0

Ж -и +;

Рис.'. 2. Структура модели выходной ошибки

15 Главе 3 разработанные вычислительные алгоритмы решения задачи П К применены к решению задачи идентификации параметров дискретов передаточной функции линейной стохастической динамической систе-ы

у{1) = аг(0 + в(0,

т

лег1) = В(<г1) =

1 + сид 1 +----1- апл

■+----1- ЬПьд~\

-1

[•) наблюдаемый входной сигнал, у(-) - ненаблюдаемый выходной сиг--\л. I]"1 - оператор запаздывания, то есть q~1y(t) = 1). Для решения 1дачи идентификации параметров 6 = [а^,..., аПа, ..., Ъпь) передаточ-

:>й (функции Н[ч ') = используется критерий

О'-— Лгспйп

II со-аш

где

=

1«

О

о 0„_„

)торыИ представляет собой расширение МПНК на случай, когда часть ■олбцои матрицы С задана точно. Таким образом, задача, рассмотренная главе 2, является частным случаем такой задачи

(СТС - = Стс1,

(И)

_ __ _1_

<Т'"~ Л]-'С + < Агпах '

^max(') - максимальное собственное число матрицы, указанной л скоби а* Для нахождения коэффициента смещения <х2 требуется знание величинi [(d,C)T(d, С)]"1. Так как вычисление обратной матрицы приводит к дс иолнительной вычислительной погрешности, то в диссертации нредложе метод, позволяющий избежать процедуры обращения матрицы. Этот мето, определяется следующей леммой.

Лемма 2. Пусть даны матрицы Ri 6 ]£("-Ох(п-о / = 0,. .., п — 1.

\ г' Рг

где р^-ска.ляр, ri-еектор, а, Ri - 'квадратная матрица размерности п — > — и пусть матрицы Ri будут связаны следующими рекуррентными coomm шениями:

т

Ri+i = Ri — ^Ц t = 0.....n- 1.

Pi

Тогда, если Rq > 0, то Ri > 0 (i = 0,.. ., п — 1) и

- :т^Т = KmARn-,.)-

^тах^Лд Jp I

Применение разработанного метода к задаче ПИК. в случае, когда, част столбцов исходной матрицы известны точно, требует лишь изменения ш числения величины

r. _ i + ö"2> »+1<».«. n-hl - S Т (') • , г ^

l Ci + M+l> l+l >11«

в алгоритме (9)—(10).

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

Основные результаты и выводы

] .Задача ПИК преобразована к расширенной совместной С.? 1Л У. что д ет возможность применять для ее решения эффективные численно усто чивые методы.

2. Проведен анализ численной обусловленности расширенной СЛЛУ, е: ответствующей задаче ПНК.

3. Разработаны подходы, позволяющие повысить численную устойчи-юсть решения задачи ПНК, на основе использования оптимального масштабного множителя в расширенной СЛАУ.

-t. Разработан специальный вариант прямого проекционного метода речения расширенной СЛАУ, который позволяет существенно уменьшить ;оличество арифметических операций, необходимых для численно устой-швого решения задачи полных наименьших квадратов.

5. Разработан метод поиска коэффициента смещения в задаче ПНК для ifirniMHo приближенных СЛАУ, не требующий процедуры обращения ма-■риц.

6. Разработан численный алгоритм вычисления состоятельных оценок 1араметров дискретных передаточных функций линейных стохастических I. m ( и м и чес. к их с ис.тем.

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

Оспопные положения диссертации отражены в следующих пу-¡ликадиях:

1. Zhdanov A.I., Shamarov P.A. The Direct Projection Method for Total .east, .Squares Problem // Abstracts oflnvited Lectures and Short Communica-ions. Delivered at the Seventh International Colloquium on Numerical Analysis iIkI Computer Science with Applications. 1998. Plovdiv, Bulgaria. P. 41.

2. Жданов А.И., Шамаров П.А. Идентификация параметров дискретной /ереднто'шой функции с помощью метода полггых наименьших квадратов У Труды восьмой научной межвузовской конференции. 1998. Самара. С.

3.

3. Жданов А.И., Шамаров H.A. Прямой проекционный метод о задаче юлиых наименьших квадратов // Автоматика и телемеханика. 2000. №4. '. 77-87.

■I. Шамаров II,А. О численной обусловленности задачи полных паи-юныних кпадралоп // Вестник Самарского филиала Московского государственного университета печати. Выпуск 1. Технология, организация копомпка п управление. Москва, 2000. С. 50-54.

Введение

Глава 1. Постановка задачи полных наименьших квадратов и обзор численных методов ее решения

1.1. Формулировка задачи полных наименьших квадратов

1.2. Применение метода полных наименьших квадратов в прикладных задачах

1.3. Обзор численных алгоритмов метода полных наименьших квадратов

1.3.1. Численные методы и подходы решения задачи ПНК

1.3.2. Методы решения плохо обусловленных СЛАУ

1.4. Выводы по главе

Глава 2. Метод расширенной системы уравнений в задаче полных наименьших квадратов

2.1. Преобразование задачи ПНК к решению расширенной системы уравнений

2.2. Применение прямого рекуррентного метода для решения задачи ПНК

2.3. Численная обусловленность расширенной системы уравнений

2.3.1. Исследование обусловленности расширенной системы уравнений в линейных задачах МНК

- 32.3.2. Исследование обусловленности расширенной системы уравнений в задачах ПНК 2.3.3. Обратный анализ ошибок в задачах ПНК

2.4. Методы поиска коэффициента смещения нормальной СЛАУ

2.5. Численное исследование разработанного алгоритма

2.6. Выводы по главе

Глава 3. Идентификация параметров дискретной передаточной функции на основе МПНК

3.1. Модели динамических линейных стационарных систем

3.2. Анализ методов идентификации параметров дискретных передаточных функций стохастических динамических систем

3.3. Применение разработанного алгоритма для задачи идентификации

3.4. Численные исследования идентификации параметров дискретной передаточной функции

3.5. Выводы по главе 3 94 Заключение

Актуальность темы. Задача отыскания эффективных способов решения систем линейных алгебраических уравнений (СЛАУ) в ее различных постановках является, по-видимому, в историческом плане одной из древнейших проблем в математике. Наличие неизбежных погрешностей (возмущений) в задании коэффициентов как в правой так и в левой (матрице) ее частях, порожденных либо неточностью самих исходных данных в той содержательной задаче, математической моделью которой является рассматриваемая система уравнений, либо конечной точностью представления чисел в ЭВМ, либо и тем и другим вместе, приводит к неопределенности искомого решения. Известно, что классические алгоритмы решения СЛАУ, основанные на концепции абсолютной точности, при наличии погрешностей не могут быть положены в основу универсальных вычислительных программ для ЭВМ в силу неустойчивости решений к погрешностям.

Проблема нахождения решений приближенных (как детерминированных, так и стохастических) СЛАУ возникает в огромном числе задач математического моделирования. К их числу принадлежат задачи регрессионного анализа с ошибками в независимых переменных [83], идентификации стохастических дискретных динамических систем, описываемых линейными разностными уравнениями [8], восстановления сигналов [82] и т. д. В настоящее время наиболее разработанной ч; является задача решения приближенных СЛАХ в которой неточно задан лишь вектор правой части, а матрица системы задана точно. Одним из наиболее эффективных и универсальных методов решения этой задачи является классический линейный метод наименьших квадратов (МНК). Это связано с тем фактом, что в настоящее время имеется достаточное число высокоэффективных (в вычислительном отношении) алгоритмов для МНК, а также, что многие статистические свойства оценок решений,полученных на основе МНК для приближенных стохастических СЛАУ (задач регрессионного анализа); не зависят от функций распределений возмущений.

Значительно менее разработанными являются методы решения приближенных СЛАУ (как детерминированных, так и стохастических) когда неточно заданы как вектор правой части, так и матрица коэффициентов СЛАУ. Одним из методов решения таких задач является метод полных наименьших квадратов (МПНК) [50], который является естественным обобщением МНК на случай приближенных СЛАУ с неточно заданной матрицей коэффициентов.

Постановка задачи полных наименьших квадратов впервые была рассмотрена академиком Ю.В. Линником (под названием " метод ортогональных проекций") применительно к задачам регрессионного анализа [17]. В дальнейшем, значительный вклад в развитие МПНК и его анализ внесли А.И. Жданов [9], A.B. Крянев [16], а также зарубежные ученые Д. Голуб (G. Golub), С. Ван Лоан (С. Van Loan) [49], [50], С. Ван Хаффел (S. Van Huffel), Д. Вандевейл (J. Vandewalle) [76], [79], А. Вьорк (А. Björk) [36].

Для стохастических задач МПНК сохраняет большинство свойств классического линейного МНК, таких, например, как независимость от конкретного вида функций распределения ошибок. Но вычислительная задача полных наименьших квадратов (ПНК) значительно сложнее, чем задача линейных наименьших квадратов. Задача ПНК является нелинейной и в большинстве случаев плохо обусловленной. Плохая обусловленность задачи не позволяет эффективно применять численно устойчивые алгоритмы без значительного увеличения числа арифметических операций, необходимых для ее решения.

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

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

Для достижения поставленной в работе цели были решены следующие задачи.

1. Преобразование исходной задачи ПНК к задаче решения совместной расширенной СЛАУ.

2. Исследование обусловленности расширенной СЛАУ, соответствующей задаче ПНК.

3. Разработка численного алгоритма для решения расширенной СЛАУ, соответствующей задаче ПНК большой размерности.

4. Исследование и выбор алгоритма для вычисления минимального сингулярного числа в задаче ПНК.

5. Решение на основе ПНК частично приближенных СЛАУ (вектор правой части и некоторая часть столбцов матрицы которой известны приближенно) в задачах параметрической идентификации дискретных передаточных функций.

6. Проведение на ЭВМ тестовых исследований разработанных алгоритмов.

Научная новизна заключается в следующем. в Разработан метод преобразования исходной задачи ПНК к задаче решения совместной расширенной СЛАУ.

• Предложена модификация расширенной СЛАУ, соответствующей ПНК, с масштабным множителем, позволяющим снизить число обусловленности исходной задачи.

• Разработан специальный вариант прямого проекционного метода для решения расширенной СЛАУ соответствующей ПНК, который позволяет существенно сократить число арифметических операций, требуемых для ее решения.

• Найдены экспериментальные оценки для оптимального масштабного множителя.

• С помощью обратного анализа ошибок проведено доказательство устойчивости данного подхода с применением оптимального масштабного множителя к расширенной СЛАУ.

• Вычислено значение оптимального множителя в зависимости от нормы искомого вектора.

• Разработан численный алгоритм идентификации параметров дискретной передаточной функции в модели выходной ошибки.

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

Методы исследований. При формулировке и доказательстве результатов используются положения линейной алгебры, теории вероятностей, теории возмущений, а также теории идентификации дискретных динамических систем. Исследования полученных методов и алгоритмов проводились на основе имитационного моделирования. При разработке программного обеспечения использовался пакет МАТЬАВ (версия 5.3).

По теме диссертации опубликовано 4 работы [84], [14], [13], [24]. Диссертация состоит из введения, трех глав, заключения и списка литературы из 84 наименований источников отечественной и зарубежной литературы.

3.5. Выводы по главе 3

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

V; / Ж Ч V w/ Vi >

Д ' <7 л -У ' Н А ' i'l

Л л *} ' .<\А .

V • • / ' • . .V» . " -V-.■-. F ^ <?• \\ I ^ AsH' \ > • v 1

U<0 \ /'

A<t> \ y<t) оценю! метода ГМК о»енк-и коррелйниоиного метоля формируемой смещенной нормальной СЛАУ может быть вычислен без обращения матриц.

2. Результаты имитационного моделирования показали высокую численную устойчивость разработанного метода в применении к задаче идентификации параметров дискретных передаточных функций. В сравнении с методом Штайглица-Макбрайда и корреляционным методом, предлагаемый алгоритм соответственно имеет более низкую вычислительную сложность решения и позволяет найти более точные оценки. Особенно преимущество по точности оценок проявляется на плохо обусловленных задачах идентификации.

- 96-Заключение

1.Задача ПНК преобразована к расширенной совместной СЛАУ, что дает возможность применять для ее решения эффективные численно устойчивые методы.

2. Проведен анализ численной обусловленности расширенной СЛАУ, соответствующей задаче ПНК. Найдена зависимость числа обусловленности расширенной матрицы расширенной системы от минимального и максимального сингулярных чисел исходной матрицы.

3. Разработаны подходы, позволяющие повысить численную устойчивость решения задачи ПНК, на основе использования оптимального масштабного множителя в расширенной СЛАУ.

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

5. Разработан метод поиска коэффициента смещения в задаче ПНК для частично приближенных СЛАУ, не требующий процедуры обращения матриц.

- 976. Разработан численный алгоритм вычисления состоятельных оценок параметров дискретных передаточных функций линейных стохастических динамических систем.

7. С помощью имитационного моделирования показана высокая эффективность разработанных алгоритмов на классе плохо обусловленных задач большой размерности. Проведенные имитационные исследования выявили ряд преимуществ разработанного метода перед известными алгоритмами решения переопределенных СЛАУ с ошибками в матрице и алгоритмами поиска параметров дискретных передаточных функций.

1. Абаффи Й., Спедикато Э. Математические методы для линейных и нелинейных уравнений: Проекционные ABS-алгоритмы.Ы.: Мир, 1996. 268 с.

2. Беклемишев Д.В. Дополнительные главы линейной алгебры. М.: Наука, 1983. 336 с.

3. Бронштейн И.Н., Семендяев К.А. Справочник по математике. М.: Наука. 1965. 608 с.

4. Воеводин В.В. Численные методы алгебры (теория и алгорифмы). М.: Наука, 1966. 248 с.

5. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984. 320 с.

6. Гантмахер Ф.Р. Теория матриц. М.:Наука, 1967. 575 с.

7. Жданов А.И. Решение некорректных стохастических линейных алгебраических уравнений регуляризованным методом максимального правдоподобия. // ЖВМиМФ. 1988. Т. 28. №9. С. 14201425.

8. Жданов А.И. Вычисление регуляризованных оценок наименьших квадратов коэффициентов авторегрессии по неточным данным // АиТ. 1990. №3. С. 110-117.

9. Жданов А.И. О приближенных стохастических системах линейных алгебраических уравнений // ЖВМиМФ, 1989. Т. 29. №12. С. 1776-1787.

10. Жданов А.И. Прямые рекуррентные а.пгоритмы решения линейных задач метода наименьших квадратов. // ЖВМиМФ. 1994. Т. 34. №6. С. 811-814

11. Жданов А.И. Прямой последовательный метод решения систем линейных алгебраических уравнений // Докл. РАН. 1997. Т. 356. т. С. 442-444

12. Жданов А.И., Кащоба O.A. Особенности применения метода наименьших квадратов для оценивания линейных разностных операторов в задачах идентификации объектов управления! / АиТ. 1979. №8. С. 86-92.

13. Жданов А.И., Шамаров П.А. Прямой проекционный метод в задаче полных наименьших квадратов // АиТ. 2000. JVM. С. 77-87.

14. Жданов А.Й., Шамаров П.А. Идентификация параметров дискретной передаточной функции с помощью метода полных наименьших квадратов / / Труды восьмой научной межвузовской конференции. 1998. Самара. С. 43.

15. Кендалл М.Дж., Стыоарт А. Статистические выводы и связи. М.: Наука, 1973. 900 с.

16. Лоусон Ч., Хенсон Р. Численное решение задач методом наименьших квадратов. М.: Наука. 1986. 230 с.

17. Лыонг Л. Идентификация систем. Теория для пользователя. М.: Наука, 1991. 432 с.

18. Парлетт Б. Симметричная проблема собственных значений. М.: Мир, 1983. 382 с.

19. Райе Д. Матричные вычисления и математическое обеспечение. М.: Мир, 1984. 264 с.

20. Савинов Г.В. Определение экстремальных собственных значений минимизацией функционалов специального вида. // ЖВМиМФ. 1985. Т. 25. №2. С. 292-295.

21. Уилкинсон Дж. X. Алгебраическая проблема собственных значений. М.: Наука, 1970. 564 с.

22. Шамаров П.А. О численной обусловленности задачи полных наименьших квадратов / / Вестник Самарского филиала Московского государственного университета печати. Выпуск 1. Технология, организация экономика и управление. Москва, 2000. С. 50-54.

23. Эйкхофф П. Основы идентификации систем управления. М.:1. Mnp, 1975. 685 c.

24. Abatzoglou T.J., Mendel J.M. Constrained total least squares // Proc. IEEE Intemat. Conf. on Acoustic, Speech and Signal Processing. 1987. Dallas. P. 1485-1488.

25. Abatzoglou T.J., Mendel J.M., Harada G.A. The constrained total least squares technique and its application to harmonic surresolution // IEEE Trans. Signal Processing. 1991 SP-39. P. 1070-1087.

26. Ahmed M.S. Estimation of difference equation parameters SfSO systems by correlation analysis j/ Int. J. Control. 1982. Vol 35. No. 4. 677-687.

27. Akaike H. Some problems in the application of the cross-spectral methods // B. Harris (Ed.) Spectral Analysis of Time Series. New York: Wiley, 1967.

28. Ammann L.P., Van Ness J.W. Converting regressions algorithms into corresponding orthogonal regression algorithms // ACM Trans. Math. Software. 1988. No. 14. P. 76-87.

29. Ammann L.P., Van Ness J.W. Standard and robust orthogonal regression // Comm. Statist. B-Simulation Comput. 1989. No. 18. P. 145-162.

30. Aoki M., Yue P.C. On certain convergence questions in system identification // SIAM J. Control. 1970. Vol. 8. No. 2. P. 239-255.

31. Aoki M., Yue P.C. On a priory estimates of some identification methods H \Zih ASME Design and Automat. Conf. 1982. Boston. P. 215-220.

32. Arioli M., Duff I.S., de Rijk P.P.M. On the augment system approach to sparce least-squares problems // Numer. Math. 1989 Vol. 55. P. 667-684.

33. Benzi M., Meyer C.D. A direct projection method for sparse linear systems // SIAM J. Sci. Comput., 1995. V. 16. No. 5. P. 1159-1176.

34. Bjork A. Handbook of numerical analysis. V. 1. North-Holland: Elsevier, 1990.

35. Bjork A. Component-wise perturbation analysis and errors bounds for linear least squares solutions // BIT. 1991. Vol. 31. P. 238-244.

36. Bjork A. Pivoting and Stability in the Augment System Method // Numerical Analysis. 1991. Proceedings of the 14th Dundee Conference. Griffiths D.F. and Watson G.A. eds. P. 1-16.

37. Bjork A. Numerical Stability of Methods for Solving Augment Systems // Contemp. Math. 1997. Vol 204. P. 51-59.

38. Bjork A., Heggernes P., Matstoms P. Methods for large scale total- 103least squares problems // Preprint. 1999. 18P.

39. Bunch J.R., Nielsen C.P., Sorensen D.C. Rank-one modification of the symmetric eigenproblem // Numer. Math. 1978. No. 31. P. 3148.

40. Fernando K.V., Nicholson H. Identification of linear systems with input and output noise: Koopmans-Levin method // IEE Proc. D. 1985. Vol. 132. P. 30-36.

41. Fierro R.D., Bunch J.R. Perturbation Theory for Orthogonal Projection Methods with Application to Least Squares and Total Least Squares // Linear Algebra and its Applications. 1996. Vol. 234. P. 71-96.

42. Fierro R.D. Golub G.H., Hansen P.C., O'Leary D.P. Regularization by Truncated Total Least Squares. Report UNIC-93-14. 1993. 20 p.

43. Erkki O., Liuyue W. Robust Fitting by Nonlinear Neural Units // Neural Networks. 1996. Vol. 9. P. 435-444.

44. Givens W. Numerical computations of the characteristic values of a real symmetric matrix. Oak Ridge National Laboratory, ORNL-1574. 1954.

45. Golub G.H., Hansen P.C., O'Leary D.P. Tikhonov regularization and total least squares // SIAM J. Matrix Anal. Appl. 2000. Vol. 21. P. 185-194.

46. Golub G.H., Van Loan C.F. Total least squares// Smoothing Techníques for Curve Estimation. 1979. T. Gasser and M. Rosenblatt eds., Springer-Verlag: New York. P. 69-76.

47. Golub G.H., Van Loan C.F. An analysis of the total least squares problem // SIAM J. Numer. Anal. 1980. No. 17, P. 883-893.

48. Golub G.H., Van Loan C.F. Matrix Computations. Baitimor MD.: John Hopkins Press, 1989.

49. Heij C., Scherrer W. Consistency of system identifícation by global total least squares // Automatica. 1999. Vol. 35. P. 993-1008.

50. Kamm J., Nagy J.G. A total least squares method for Toeplitz systems of equations // BIT. 1998. No. 38. P. 521-534.

51. Koopmans T. Linear Regression Analysis of Economic Time Series. N.V. Haarlem, Netherlands: De Erven F. Bohn, 1937

52. Levin M. Estimation of a System Pulse Transfer Function in the Presence of Noise // IEEE Trans. Automat. Contr. 1964. Vol. AC-9. No. 3. P. 229-235.

53. Madansky A. The fítting of straight lines when both variables are subject to error // J. Amer. Statist. Assoc. 1959. No. 54. P. 173205.

54. Matstoms P. Sparse QR factorization in MATLAB // Trans. Math. Software.1994. No. 20. P. 136-159.

55. Moonen M., De Moore B., Vandenberhg L., Vandewalle J. On-line and off-line identifícation of linear state-space models // Internat. J.- 105

56. Control. 1989. Vol. 49. P. 219-232.

57. Musheng W. Algebraic relations between the least squares and total least squares problems with more than one solution // Nurner. Math. 1992. Vol. 62. P. 123-148.

58. Musheng W. Perturbation theory for the Eckart-Young-Mirsky theorem and the constrained total least squares problem // Linear Algebra and its Applications. 1998. Vol. 280. P. 267-287.

59. Navia-Vazques A., Fiqueras-Vidal A.R. Total least squares for block training of neural networks // Neurocomputing. 1999. Vol. 25. P. 213-217.

60. Pearson K. On lines and planes of closest fit to points in space // Phil. Mag. 1901. No. 2. P. 559-572.

61. Peters G., Wilkinson J.H. Inverse iteration, ill-conditioned equations and Newton's method // SIAM Review, 1979. No 3. P. 339-360.

62. Pisarenko V.P. The retrieval of harmonics from a covariance function 11 Geophys. J. Roy. Astron. Soc. 1973. Vol. 33. P. 347-366.

63. Rahman M.A., Yu K.B. Total least squares approach for frequency estimation using linear prediction J/ IEEE Trans. Acoust. Speech Signal Process. 1987. ASSP-35. P. 1440-1454.

64. Spáth H. Orthogonal least squares fitting with linear manifolds // Numer. Math. 1986. Vol. 48. P. 441-445.

65. Soderstrom T., Stoica P. On the stability of dynamic models obtained by least squares identification // IEEE Trans. Automat. Con-tr. 1981. Vol. AC-26. No. 2. P. 575-577.

66. Steiglitz K., McBride L.E. A technique for the identification of linear systems // IEEE Trans. Automat. Contr. 1965. Vol. AC-10. No. 5. P. 461-464.

67. Stoica P., Soderstrom T. The Steiglitz-McBride identification algorithm revised convergence analysis and accuracy aspects // IEEE Trans. Automat. Contr. 1981. Vol. AC-26. No. 3. P. 712-717.

68. Stoica P., Soderstrom T. Bias correction in least-squares identification // Int. J. Control, 1982. V. 35. No. 3. P. 449-457.

69. Stoica P., Soderstrom T. Optimal Instrumental-variable Methods for Identification of Multivariate Linear Systems / / Automatica. 1983. Vol. 19. No. 4. P. 425-429.

70. Szyld D.B. Criteria for combinig inverse and Rayleigh quontient iteration // SIAM J. Numer. Anal. 1988. No. 25. P. 1369-1375.

71. Trefethen L.N., Bau D. Numerical Linear Algebra. SIAM, 1997. -373 p.- 10776. Van Huffel S., Vandewalle J. Algebraic connection between the least squares and total least squares problems j/ Numer. Math. 1989. Vol. 55. P. 431-449.

72. Van Huífel S., Vandewalle J. Comparison of total least squares and instrumental variable methods for parameter estimation of transfer function models // Internat. J. Control. 1989. Vol. 50. P. 1039-1056.

73. Van Huffel S., Vandewalle J. On the accuracy of total least squares technicues in the presence of errors on all data j/ Automática. 1989 Vol. 25. P. 765-769.

74. Van Huffel S., Vandewalle J. The Total Least Squares Problem: Computational Aspects and Analysis, SIAM 1990. 313 p.

75. Wald A. Asymptotic properties of the maximum-likehood estimate of an unknown parameter of a discrete stochastic process // An. Math. Statist. 1948. No. 19. P. 40-46.

76. Ward R.K. Comparison and diagnostic of errors for six parameter estimation methods // Internat. J. Sys. Sci. 1984. No. 15. P. 745758.

77. Younan N.H., Fan X. Signal restoration via the regularized constrained total least squares // Signal Processing. 1998. Vol. 71. P. 85-93.

78. Ot^&^bYll/1.'. *,íi %ЕИ5ЛЯ0ТСГ.А1. ОП316-00