Диссертация (1150576), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

Пусть – регулярная по строкам разреженная матрица задачи−(3.3), где и – регулярные векторы, и Δ = (() )1/2 . Тогда минимум взадаче (3.3) равен Δ и достигается на любом векторе , который удовлетворяет условиюΔ−1 − ≤ ≤ Δ.(3.7)Доказательство. Заметим, что определяемое неравенством (3.7) множество непусто.

Действительно, из того, что матрица является разреженной, следуетнеравенство− ≤ Δ2 − ,после умножения которого на Δ−1 справа получаемΔ−1 − ≤ Δ.Покажем, что все векторы , которые удовлетворяют двойному неравенству(3.7), являются решениями системы (3.5). В силу того, что правое неравенствов (3.7) совпадает со вторым в системе (3.5), достаточно проверить выполнениенеравенства ≥ Δ−1 .Так как матрица – регулярна по строкам, то ≤ − .

Умножив левоенеравенство из двойного неравенства (3.7) на слева, получаем, чтоΔ−1 ≤ Δ−1 − ≤ ,откуда следует требуемое неравенство системы (3.5).62Теперь сформулируем лемму, которая обеспечивает полное решение задачи(3.3).Лемма 8. Пусть – регулярная по строкам разреженная матрица задачи−(3.3), где и – регулярные векторы, и Δ = (() )1/2 . Обозначим через множество матриц, полученных из путем сохранения по одному ненулевому элементу в каждой строке и обнулением остальных.Тогда минимум в задаче (3.3) равен Δ, а все регулярные решения образуют семейство решений, каждое из которых определяется условиемΔ−1 −1 ≤ ≤ Δ,1 ∈ .(3.8)Доказательство. Как было показано выше, все решения задачи (3.3) задаютсясистемой (3.5). Следовательно, для доказательства леммы требуется проверить,что каждому решению системы (3.5) соответствует некоторая матрица 1 ∈ и наоборот.Пусть вектор является решением системы (3.5).

Рассмотрим векторноенеравенство ≥ Δ−1 и исследуем каждое из соответствующих скалярных неравенств, чтобы определить максимальное слагаемое в левой части. Несложно видеть, что найдетсяматрица 1 ∈ с ненулевыми элементами в каждой строке, которые соответствуют этим максимальным слагаемым.Теперь предположим, что – решение неравенства (3.8) для некоторой матрицы 1 .

Так как матрица 1 регулярна по строкам и 1 ≤ , то− ≤ 1 −1 ≤ 1 .Умножая левую часть неравенства (3.8) на слева, получаем−1 ≥ Δ−1 −1 ≥ Δ .Из этого следует, что является решением системы (3.5), а значит и задачи(3.3).63Отметим, что у различных множеств решений из семейства, описанного влемме 8, могут быть пересекающиеся подмножества.Для получения решения в параметрическом виде докажем следующую теорему.Теорема 5. Пусть – регулярная по строкам разреженная матрица задачи (3.3), где и – регулярные векторы, и Δ = (()− )1/2 .

Обозначимчерез множество матриц, полученных из путем сохранения по одномуненулевому элементу в каждой строке и обнулением остальных, а через – матрицу, столбцами которой являются векторы 1 = Δ−1 −1 для всехматриц 1 ∈ .Тогда минимум в задаче (3.3) равен Δ, а все регулярные решения имеютвид = ⊕ , ≤ Δ,1 = 1.(3.9)Доказательство. Пусть множество содержит матриц. Для каждого =1, . . . , возьмем матрицу ∈ и определим левую часть = Δ−1 − неравенства (3.8). Учитывая, что правая часть неравенства всегда равна Δ , семейство решений описывается следующим набором двойных неравенств:1 ≤ 1 ≤ Δ, .

. . , ≤ ≤ Δ.Рассмотрим произвольные векторы 1 , . . . , , для которых соответствующие двойные неравенства выполняются. По следствию 1 множество решенийзадачи (3.3) замкнуто относительно операции взятия выпуклой линейной комбинации. Следовательно, если 1 ⊕ · · · ⊕ = 1, то вектор 1 1 ⊕ · · · ⊕ также является решением.Покажем, что общее решение задачи можно записать в виде1 1 ⊕ · · · ⊕ ≤ ≤ Δ,1 ⊕ · · · ⊕ = 1.(3.10)Если вектор – решение задачи (3.3), то он принадлежит семейству решений, определяемому нижней границей = Δ−1 − , которая задается некоторой матрицей ∈ .

Чтобы представить вектор в форме (3.10), положимкоэффициент равным 1, а все остальные коэффициенты обнулим.64Пусть вектор удовлетворяет системе (3.10). Тогда существует такой индекс, для которого выполняются соотношения = 1 иΔ−1 − = ≤ ≤ Δ,откуда следует, что принадлежит семейству решений, образованному матрицей .Построим матрицу = (1 , . .

. , ), используя векторы в качестве столбцов, и введем вектор = (1 , . . . , ) . Теперь двойное неравенство и равенствосистемы (3.10) можно записать в векторной форме как ≤ ≤ Δ,1 = 1.С помощью вектора = (1 , . . . , ) запишем двойное неравенство в эквивалентной форме в виде системы = ⊕ , ≤ Δ.Объединение этой системы с условием 1 = 1 приводит к решению (3.9).В качестве следствия полученного результата представим решение задачи(3.1), которая является частным случаем задачи (3.3).Следствие 2. Пусть – регулярная по строкам разреженная матрица задачи (3.1), где – регулярный вектор и Δ = (((− )− )− )1/2 .

Обозначимчерез множество матриц, полученных из путем сохранения по одномуненулевому элементу в каждой строке и обнулением остальных, а через – матрицу, столбцами которой являются векторы 1 = Δ−1 −1 для всехматриц 1 ∈ .Тогда минимум в задаче (3.3) равен Δ, а все регулярные решения имеютвид = ⊕ , ≤ Δ(− )− ,1 = 1.65Таким образом, для задачи псевдочебышевской аппроксимации было представлено множество всех решений, которые в дальнейшем могут быть отобраныс учетом дополнительных требований или ограничений.3.5Процедуры построения полного решенияПеребор всевозможных матриц 1 ∈ для построения подмножеств семейства решений задачи в соответствии с результатом теоремы 5 может представлять определенные трудности.

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

Пусть выбран ненулевойэлемент в одной из оставшихся строк, например элемент ̃︀ в строке и столбце , значение которого фиксируется, а остальные элементы в этой строке замещаются нулями.Всякий вектор = ( ), который является решением задачи (3.3), удовлетворяет системе (3.5), в частности, ее первому неравенству в форме̃︀ ≥ Δ−1 .Скалярное неравенство для строки , где все элементы кроме ̃︀ равны 0,записывается в виде̃︀ ≥ Δ−1 ,что эквивалентно неравенству ≥ Δ−1̃︀−1 .66В столбце возьмем элемент ̃︀ , который расположен в одной из еще нерассмотренных строк . При выполнении условия̃︀ −1 −1 ≥ ̃︀ ,которое эквивалентно условию̃︀ ≥ ̃︀ −1 ,имеем следующую цепочку неравенств:−1 −1̃︀ ≥ ̃︀ −1 ≥ Δ−1 .

Δ ̃︀Тогда неравенство1 1 ⊕ · · · ⊕ ≥ Δ−1 в системе (3.5) выполняется вне зависимости от значений для всех ̸= . Вэтом случае дальнейшее исследование ненулевых элементов ̃︀ в строке не может дать новых решений. Эти элементы можно заменить нулями, не нарушаянеравенство, что уменьшает число альтернатив, которые требуется рассмотреть.Заметим, что для проверки условия̃︀ −1 −1 ≥ ̃︀̂︀ на элемент −1 ,удобно предварительно умножить каждую строку матрицы а затем исследовать элементы полученной матрицы, которую обозначим через̂︀′ = (̂︀′ ).̂︀′ преобладают элементы, являющиесяЕсли в какой-то строке матрицы минимальными ненулевыми элементами в своих столбцах, то, вероятно, стоит начать перебор с подобной строки.

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

Пусть – матрица, столбцы которой определяют нижние границы для некоторого набора подмножеств семейства решений (3.8),а 1 = Δ−1 1 , где 1 ∈ , – еще одна граница. Тогда граница 1 являетсянесущественной, если выполняется неравенство−1 (−1 ) ≥ 1.(3.11)Доказательство. Подмножество с новой нижней границей 1 уже принадлежит семейству решений и может не учитываться, если найдется выпуклая комбинация нижних границ подмножеств семейства, которая не меньше, чем 1 .Учитывая, что имеющиеся нижние границы подмножеств образуют столбцыматрицы , это условие эквивалентно выполнению неравенства ≤ 1 длянекоторого вектора такого, что 1 = 1.Решение неравенства относительно вектора с помощью леммы 1.4 дает− ≤ (−1 ) .Для выполнения условия 1 = 1 необходимо и достаточно, чтобы хотя бы−одна координата вектора (−1 ) была не меньше 1.

Характеристики

Список файлов диссертации