устройство для решения задачи наименьших квадратов

Формула изобретения

1. УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ НАИМЕНЬШИХ КВАДРАТОВ, содержащее N вычислительных модулей, где N число неизвестных системы линейных алгебраических уравнений, причем информационный вход устройства подключен к информационному входу первого вычислительного модуля, информационный вход i-го вычислительного модуля (i 1,N 1) подключен к информационному входу (i + 1)-го вычислительного модуля, информационный выход N-го вычислительного модуля подключен к выходу устройства, тактовый вход которого подключен к тактовым входам всех вычислительных модулей, отличающееся тем, что первый, второй, третий и четвертый управляющие входы подключены соответственно к первому, второму, третьему и четвертому управляющим входам первого вычислительного модуля, первый, второй, третий и четвертый управляющие входы i-го вычислительного модуля (i 1, N 1) подключены соответственно к первому, второму, третьему и четвертому управляющим входам (i + 1)-го вычислительного модуля, при этом каждый вычислительный модуль содержит узел вычисления величины из квадратного корня суммы квадратов двух чисел, узел вычисления обратной величины числа, шесть умножителей, сумматор, вычитатель, два регистра, две группы регистров, блок управления, двадцать три группы элементов И, элемент И, девять групп элементов ИЛИ, четыре элемента ИЛИ, причем информационный вход вычислительного модуля подключен к информационному входу первого регистра, выход которого подключен к первым входам первого и четвертого умножителей, элементов И первой, второй и третьей групп и к первому входу узла вычисления величины из квадратного корня суммы квадратов двух чисел, второй вход которого подключен к выходу второго регистра, а выход к первым входам элементов И четвертой группы, выход которых подключен к первым входам элементов ИЛИ первой группы, вторые входы которых подключены к соответствующим выходам элементов И пятой группы, а выходы к входу узла вычисления обратной величины числа, выход которого подключен к первым входам элементов И шестой, седьмой, восьмой и девятой групп, выход второго регистра подключен к первым входам второго, третьего умножителей, элементов И пятой, десятой и одиннадцатой групп, первый, второй, третий и четвертый входы блока управления подключены соответственно к первому, второму, третьему и четвертому входам вычислительного модуля, а первый, второй, третий и четвертый выходы - соответственно к первому, второму, третьему и четвертому управляющим выходам вычислительного модуля, прямой выход второго умножителя подключен к первым входам элементов И двенадцатой группы, а инверсный выход к первым входам элементов И тринадцатой группы, выходы которых подключены к соответствующим первым входам элементов ИЛИ второй группы, выходы которых подключены к информационному выходу вычислительного модуля, выход первого элемента ИЛИ подключен к вторым входам элементов И восьмой группы, выходы которых подключены к второму входу первого умножителя, выход которого подключен к первым входам элементов И четырнадцатой группы, выход первого регистра первой группы подключен к первым входам элементов И пятнадцатой и шестнадцатой групп, пятого умножителя и второму входу третьего умножителя, выход первого регистра второй группы подключен к первым входам элементов И семнадцатой и восемнадцатой группы и второму входу четвертого умножителя, выходы третьего и четвертого умножителей подключены соответственно к первому и второму входам сумматора, выход которого подключен к первым входам элементов И девятнадцатой группы, выходы элементов И седьмой и шестнадцатой групп подключены соответственно к первым и вторым входам элементов ИЛИ третьей группы, выходы которых подключены к второму входу второго умножителя, выход второго элемента ИЛИ подключен к вторым входам элементов И пятой группы, выход элемента И подключен к синхровходу второго регистра, выход третьего элемента ИЛИ подключен к вторым входам элементов И первой группы, выходы элементов И девятнадцатой, первой и шестой групп подключены соответственно к первым, вторым и третьим входам элементов ИЛИ четвертой группы, выходы которой подключены к информационному входу второго регистра, вход установки в "0" которого подключен к пятому выходу блока управления, выходы элементов И семнадцатой, двадцатой и четырнадцатой групп подключены соответственно к первым, вторым и третьим входам элементов ИЛИ пятой группы, выход которых подключен к информационному входу второго регистра второй группы, выход i-го регистра второй группы подключен к информационному входу (i + 1)-го регистра, выход (K + 1)-го регистра второй группы подключен к информационному входу первого регистра второй группы, выход элементов И пятнадцатой, двадцать третьей, девятой и двенадцатой групп подключены соответственно к первым, вторым, третьим и четвертым входам шестой группы элементов ИЛИ, выходы которых подключены к информационному входу второго регистра первой группы, выход i-го регистра первой группы подключен к информационному входу (i + 1)-го регистра первой группы, выход (K + 1)-го регистра первой группы подключен к информационному входу первого регистра первой группы, выход элементов И второй и десятой групп подключены соответственно к первым и вторым входам элементов ИЛИ седьмой группы, выходы которых подключены к первому входу шестого умножителя, выходы элементов И восемнадцатой и двадцать первой групп подключены соответственно к первым и вторым входам восьмой группы элементов ИЛИ, выходы которых подключены к второму входу шестого умножителя, выходы элементов И третьей и одиннадцатой групп подключены соответственно к первым и вторым входам элементов ИЛИ девятой группы, выходы пятого и шестого умножителей подключены соответственно к первому и второму входам вычитателя, выход которого подключен к первым входам элементов И двадцать второй группы, выход которых подключен к вторым входам элементов ИЛИ второй группы, шестой выход блока управления подключен к первым входам элементов И двадцатой и двадцать третьей групп и третьего элемента ИЛИ, седьмой выход блока управления подключен к вторым входам элементов И четвертой, шестой, седьмой и четырнадцатой групп первого элемента ИЛИ и первому входу четвертого элемента ИЛИ, восьмой выход блока управления подключен к вторым входам элементов И третьей, десятой, восемнадцатой и девятнадцатой групп, девятый выход блока управления подключен к первым входам элемента И и второго элемента ИЛИ, десятый выход блока управления подключен к первому входу первого элемента ИЛИ и вторым входам второго и четвертого элементов ИЛИ, одиннадцатый выход блока управления подключен к вторым входам элементов И пятнадцатой группы, двенадцатый выход блока управления подключен к вторым входам элементов И семнадцатой группы, тринадцатый выход блока управления подключен к вторым входам элементов И второй, одиннадцатой и двадцать первой группы, четырнадцатый выход блока управления подключен к второму входу третьего элемента ИЛИ, пятнадцатый выход блока управления подключен к вторым входам элементов И двадцать второй группы, шестнадцатый выход блока управления подключен к вторым входам элементов И девятой группы, семнадцатый выход блока управления подключен к вторым входам элементов И тринадцатой и шестнадцатой групп, единичный вход вычислительного модуля подключен к первым входам элементов И двадцать первой группы и вторым входам элементов И двадцатой группы, нулевой вход вычислительного модуля подключен к вторым входам элементов И двадцать третьей группы, тактовый вход вычислительного модуля подключен к синхровходам первого регистра, всех регистров первой и второй групп и пятому входу блока управления.

2. Устройство по п. 1, отличающееся тем, что блок управления содержит шесть триггеров, три группы триггеров, двенадцать элементов И, два элемента ИЛИ, два элемента ИЛИ-НЕ, три элемента НЕ, причем первый вход блока управления подключен к входу первого элемента НЕ, первым входам четвертого, пятого элементов И и информационному входу первого триггера первой группы, выход i-го триггера первой группы подключен к информационному входу (i + 1)-го триггера первой группы, выход (K + 3)-го триггера первой группы подключен к первому выходу блока управления, выход первого элемента НЕ подключен к первым входам первого, второго и третьего элементов И, второй вход блока управления подключен к входу второго элемента НЕ, вторым входам второго и третьего элементов И и информационному входу первого триггера второй группы, выход i-го триггера второй группы подключен к информационному входу (i +1)-го триггера второй группы, выход (K + 3)-го триггера второй группы подключен к второму выходу блока управления, выход второго элемента НЕ подключен к вторым входам первого, четвертого и пятого элементов И, третий вход блока управления подключен к входу третьего элемента НЕ, третьим входам первого, третьего и пятого элементов И и информационному входу первого триггера третьей группы, выход i-го триггера третьей группы подключен к информационному входу (i + 1)-го триггера третьей группы, выход (K + 3)-го триггера третьей группы подключен к третьему выходу блока управления, выход третьего элемента НЕ подключен к третьим входам второго и четвертого элементов И, выходы с первого по пятый элементов И подключены к информационным входам соответственно с первого по пятый триггеров, выход первого элемента И подключен к пятому выходу блока управления, четвертый вход которого подключен к первому входу шестого элемента И, второй вход которого подключен к выходу третьего элемента И, а выход к первому входу первого элемента ИЛИ, выход которого подключен к информационному входу шестого триггера, прямой выход которого подключен к первым входам одиннадцатого, двенадцатого элементов И и четвертому выходу блока управления, а инверсный выход к первым входам восьмого, девятого и десятого элементов И, выход пятого элемента И подключен к первому входу седьмого элемента И, второй вход которого подключен к единичному входу блока управления, а выход к второму входу первого элемента ИЛИ, прямой выход первого триггера подключен к второму входу восьмого элемента И, первому входу второго элемента ИЛИ и четвертому выходу блока управления, инверсный выход первого триггера подключен к второму входу девятого элемента И, выход второго триггера подключен к третьим входам восьмого и девятого элементов И и второму входу одиннадцатого элемента И, выход третьего триггера подключен к вторым входам десятого, двенадцатого элементов И и пятнадцатому выходу блока управления, выходы четвертого триггера подключен к первому входу первого элемента ИЛИ-НЕ и шестнадцатому выходу блока управления, выход пятого триггера подключен к семнадцатому выходу блока управления, выход восьмого элемента И подключен к вторым входам второго элемента ИЛИ и первого элемента ИЛИ-НЕ и первому входу второго элемента ИЛИ-НЕ, выход девятого элемента И подключен к третьим входам второго элемента ИЛИ и первого элемента ИЛИ-НЕ и второму входу второго элемента ИЛИ-НЕ, выход десятого элемента И подключен к четвертому входу второго элемента ИЛИ, выход одиннадцатого элемента И подключен к четвертому входу первого элемента ИЛИ-НЕ, выходы восьмого, девятого, десятого элементов И, второго элемента ИЛИ, одиннадцатого элемента И, первого и второго элементов ИЛИ-НЕ и двенадцатого элемента И подключены соответственно к шестому по тринадцатый выходам блока управления, пятый вход которого подключен к синхровходам всех триггеров блока управления.

Описание изобретения к патенту

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

Известно устройство для решения задачи наименьших квадратов путем решения системы линейных алгебраических уравнений, содержащее К х N вычислительных модулей, где К число уравнений, N число неизвестных [1]

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

Наиболее близким по технической сущности к предложенному является устройство, решающее задачу наименьших квадратов и содержащее N вычислительных модулей, где N число неизвестных системы линейных алгебраических уравнений [2]

Недостатком такого устройства является низкое быстродействие; время решения системы линейных алгебраических уравнений равно ((N + M)(K + N) + N 1) тактов, где К число уравнений, М число столбцов в правой части системы линейных алгебраических уравнений.

Предложенное для решения задачи наименьших квадратов содержит N вычислительных модулей, где N число неизвестных системы линейных алгебраических уравнений, причем информационный вход 1, первый 2₁, второй 2₂, третий 2₃ и четвертый 3 управляющие входы устройства подключены соответственно к информационному входу, первому, второму, третьему и четвертому управляющим входам первого вычислительного модуля 5₁, информационный выход, первый, второй, третий и четвертый управляющие выходы 5_i-го вычислительного модуля (i ) подключены соответственно к информационному входу, первому, второму, третьему и четвертому управляющим входам 5 _i+1-го вычислительного модуля, информационный выход 5_N-го вычислительного модуля подключен к выходу устройства, тактовый вход 4 которого подключен к тактовым входам всех вычислительных модулей, при этом вычислительный модуль содержит узел 13 вычисления величины из квадратного корня суммы квадратов двух чисел, узел 14 вычисления обратной величины числа, шесть умножителей 15 20, сумматор 21, вычитатель 22, два регистра 23 и 24, две группы регистров 25 и 26, блок управления 27, двадцать три группы элементов И 28 50, элемент И 51, девять групп элементов ИЛИ 52-60, четыре элемента ИЛИ 61 64, причем информационный вход 7 вычислительного модуля подключен к информационному входу первого 23 регистра, выход которого подключен к первым входам первого 15 и второго 16 умножителей, первой 29, второй 46 и третьей 49 групп элементов И и к первому входу узла 13 вычисления величины из квадратного корня суммы квадратов двух чисел, второй вход которого подключен к выходу второго 24 регистра, а выход к первым входам элементов И 31 четвертой группы, выход которых подключен к первым входам элементов ИЛИ 54 первой группы, вторые входы которых подключены к соответствующим выходам элементов И 30 пятой группы, а выходы к входу узла 14 вычисления обратной величины числа, выход которого подключен к первым входам элементов И шестой 33, седьмой 34, восьмой 37 и девятой 40 групп, выход второго регистра 24 подключен к первым входам второго 16, третьего 19 умножителей, элементов И пятой 30, десятой 48 и одиннадцатой 50 групп, первый, второй, третий и четвертый входы блока управления подключены соответственно к первому 8, второму 9, третьему 10 и четвертому 11 входам вычислительного модуля, а первый, второй, третий и четвертый выходы соответственно к первому 66, второму 67, третьему 68 и четвертому 69 управляющим выходам вычислительного модуля, прямой выход второго умножителя 16 подключен к первым входам элементов И 41 двенадцатой группы, а инверсный выход к первым входам элементов И 45 тринадцатой группы, выходы которых подключены к соответствующим первым входам элементов ИЛИ 58 второй группы, выходы которых подключены к информационному выходу 65 вычислительного модуля, выход первого элемента ИЛИ 63 подключен к вторым входам элементов И 37 восьмой группы, выходы которых подключены к второму входу первого умножителя 15, выход которого подключен к первым входам элементов И 36 четырнадцатой группы, выход первого регистра 25₁первой группы подключен к первым входам элементов И пятнадцатой 42 и шестнадцатой 32 групп, четвертого умножителя 18 и второму входу третьего умножителя 19, выход первого регистра 26₁ второй группы подключен к первым входам элементов И семнадцатой 38 и восемнадцатой 43 групп и второму входу пятого умножителя 20, выходы третьего 19 и пятого 20 умножителей подключены соответственно к первому и второму входам сумматора 21, выход которого подключен к первым входам элементов И 28 девятнадцатой группы, выходы элементов И седьмой 34 и шестнадцатой 32 групп подключены соответственно к первым и вторым входам элементов ИЛИ 53 третьей группы, выходы которых подключены к второму входу второго умножителя 16, выход второго элемента ИЛИ 62 подключен к вторым входам элементов И 30 пятой группы, выход элемента И 51 подключен к синхровходу второго регистра 24, выход третьего элемента ИЛИ 61 подключен к вторым входам элементов И 29 первой группы, выходы элементов И девятнадцатой 28, первой 29 и шестой 33 групп подключены соответственно к первым, вторым и третьим входам элементов ИЛИ 52 четвертой группы, выходы которых подключены к информационному входу второго регистра 24, вход установки в нуль которого подключен к пятому выходу блока управления 27, выходы элементов И семнадцатой 38, двадцатой 35 и четырнадцатой 36 групп подключены соответственно к первым, вторым и третьим входам элементов ИЛИ 55 пятой группы, выход которых подключен к информационному входу второго регистра 26₂ второй группы, выход 26i-го регистра второй группы (i ) подключен к информационному входу 26 _i+1-го регистра, выход 26_К+1-го регистра второй группы подключен к информационному входу первого регистра 26₁ второй группы, выход элементов И пятнадцатой 42, двадцать третьей 39, девятой 40 и двенадцатой 41 групп подключены соответственно к первым, вторым, третьим и четвертым входам шестой 56 группы элементов ИЛИ, выходы которых подключены к информационному входу второго регистра 25₂ первой группы, выход 25_i-го регистра первой группы (i ) подключен к информационному входу 25 _i+1-го регистра первой группы, выход 25_К+1-го регистра первой группы подключен к информационному входу первого регистра 25₁ первой группы, выходы элементов И второй 46 и десятой 48 групп подключены соответственно к первым и вторым входам элементов ИЛИ 59 седьмой группы, выходы которых подключены к первому входу шестого умножителя 17, выходы элементов И восемнадцатой 43 и двадцать первой 44 групп подключены соответственно к первым и вторым входам восьмой 57 группы элементов ИЛИ, выходы которых подключены ко второму входу шестого умножителя 17, выходы элементов И третьей 49 и одиннадцатой 50 групп подключены соответственно к первым и вторым входам элементов ИЛИ 60 восьмой группы, выходы четвертого 18 и шестого 17 умножителей подключены соответственно к первому и второму входам вычитателя 22, выход которого подключен к первым входам элементов И 47 двадцать второй группы, выходы которых подключены к вторым входам элементов ИЛИ 58 второй группы, шестой выход блока управления 27 подключен к первым входам элементов И двадцатой 35 и двадцать третьей 39 групп и третьего элемента ИЛИ 61, седьмой выход блока управления 27 подключен к вторым входам элементов И четвертой 31, шестой 33, седьмой 34 и четырнадцатой 36 групп и первому входу пятого элемента ИЛИ 64, восьмой выход блока управления 27 подключен к вторым входам элементов И третьей 49, десятой 48, восемнадцатой 43 и девятнадцатой 28 групп, девятый выход блока управления 27 подключен к первым входам элемента И 51 и второго элемента ИЛИ 62, десятый выход блока управления 27 подключен к первому входу первого элемента ИЛИ 63 и вторым входам второго 62 и пятого 64 элементов ИЛИ, одиннадцатый выход блока управления 27 подключен к вторым входам элементов И 42 пятнадцатой группы, двенадцатый выход блока управления 27 подключен к вторым входам элементов И 38 семнадцатой группы, тринадцатый выход блока управления 27 подключен к вторым входам элементов И второй 46, одиннадцатой 50 и двадцать первой 44 групп и первого элемента ИЛИ, четырнадцатый выход блока управления 27 подключен ко второму входу третьего элемента ИЛИ 61, пятнадцатый выход блока управления 27 подключен к вторым входам элементов И 47 двадцать второй группы, шестнадцатый выход блока управления 27 подключен к вторым входам элементов И 40 девятой группы, семнадцатый выход блока управления 27 подключен к вторым входам элементов И 45 тринадцатой группы, единичный вход вычислительного модуля подключен к первым входам элементов И 44 двадцать первой группы и вторым входам элементов И 35 двадцатой группы, нулевой вход вычислительного модуля подключен к вторым входам элементов И 39 двадцать третьей группы, тактовый вход 12 вычислительного модуля подключен к синхровходам первого регистра, всех регистров первой 25 и второй 26 групп и шестому входу блока управления 27. Блок управления 27 содержит шесть триггеров 75 80, три группы триггеров 81 83, двенадцать элементов И 84 95, два элемента ИЛИ 96, 97, два элемента ИЛИ-НЕ 98, 99, три элемента НЕ 100 102, причем первый 70 вход блока управления подключен к входу первого элемента НЕ 100, первым входам четвертого 87 и пятого 88 элементов И и информационному входу первого триггера 81₁ первой группы, выход 81i-го триггера первой группы (i ) подключен к информационному входу 81_i+1-го триггера первой группы, выход 81_К+3-го триггера первой группы подключен к первому 103 выходу блока управления, выход первого элемента НЕ 100 подключен к первым входам первого 84, второго 85 и третьего 86 элементов И, второй 71 вход блока управления подключен к входу второго элемента НЕ 101, вторым входам второго 85 и третьего 86 элементов И и информационному входу первого триггера 82₁ второй группы, выход 82_i-го триггера второй группы (i ) подключен к информационному входу 82_i+1-го триггера второй группы, выход 82_К+3-го триггера второй группы подключен к второму 104 выходу блока управления, выход второго элемента НЕ 101 подключен к вторым входам первого 84, четвертого 87 и пятого 88 элементов И, третий 72 вход блока управления подключен к входу третьего элемента НЕ 102, к третьим входам первого 84, третьего 86 и пятого 88 элементов И и информационному входу первого триггера 83₁ третьей группы, выход 83 i-го триггера третьей группы (i ) подключен к информационному входу 83 i+1-го триггера третьей группы, выход 83 К+3-го триггера третьей группы подключен к третьему 105 выходу блока управления, выходы с первого по пятый элементов И 84 88 подключены к информационным входам соответственно с первого по пятый триггеров 76-80, выход первого элемента И 84 подключен к пятому 107 выходу блока управления, четвертый 73 вход которого подключен к первому входу шестого элемента И 94, второй вход которого подключен к выходу третьего элемента И 86, а выход к первому элементу ИЛИ 96, выход которого подключен к информационному входу шестого триггера 75, прямой выход которого подключен к первым входам одиннадцатого 92, двенадцатого 93 элементов И и четвертому 106 выходу блока управления, а инверсный выход к первым входам восьмого 89, девятого 90 и десятого 91 элементов И, выход пятого элемента И 88 подключен к первому входу седьмого элемента И 95, второй вход которого подключен к единичному входу блока управления, а выход к второму входу первого элемента ИЛИ 96, выход первого триггера 76 подключен к второму входу восьмого элемента И 89, первому входу второго элемента ИЛИ 97 и четырнадцатому 116 выходу блока управления, инверсный выход первого триггера 76 подключен к второму входу девятого элемента И 90, выход второго триггера 77 подключен к третьим входам восьмого 89 и девятого 90 элементов И и вторым входам одиннадцатого 92 элемента И, выход третьего 78 триггера подключен к вторым входам десятого 91, двенадцатого 93 элементов И и к пятнадцатому 117 выходу блока управления, выход четвертого 79 триггера подключен к первому входу первого элемента ИЛИ-НЕ 98 и шестнадцатому 118 выходу блока управления, выход пятого триггера 80 подключен к семнадцатому 119 выходу блока управления, выход восьмого элемента И 89 подключен к вторым входам элемента ИЛИ 97 и первого элемента ИЛИ-НЕ 98 и первому входу второго элемента ИЛИ-НЕ 99, выход девятого элемента И 90 подключен к третьим входам второго элемента ИЛИ 97 и первого элемента ИЛИ-НЕ 98 и второму входу второго элемента ИЛИ-НЕ 99, выход десятого элемента И 91 подключен к четвертому входу второго элемента ИЛИ 97, выход одиннадцатого элемента И 92 подключен к четвертому входу первого элемента ИЛИ-НЕ 98, выходы восьмого 89, девятого 90, десятого 91 элементов И, второго элемента ИЛИ 97, одиннадцатого элемента И 92, первого 98 и второго 99 элементов ИЛИ-НЕ и двенадцатого элемента И 93 подключены соответственно выходам с шестого по тринадцатый 108-115 блока управления, пятый вход 74 которого подключен к синхровходам всех триггеров блока управления.

На фиг. 1 представлена структурная схема устройства для решения задачи наименьших квадратов; на фиг. 2 структурная схема вычислительного модуля; на фиг. 3 структурная схема блока управления.

Устройство для решения задачи наименьших квадратов (фиг. 1) содержит информационный вход 1; первый 2₁, второй 2₂, третий 2₃ и четвертый 3 управляющие входы, тактовый вход 4, вычислительные модули 5_i(i ) и выход 6.

Вычислительный модуль 5 (фиг. 2) содержит информационный вход 7, первый 8, второй 9, третий 10 и четвертый 11 управляющие входы, тактовый вход 12, узел 13 вычисления величины , узел 14 вычисления обратной величины числа, первый 15, второй 16, третий 17, четвертый 18, пятый 19 и шестой 20 умножители, сумматор 21, вычитатель 22, первый 23 и второй 24 регистры, первую 25_i и вторую 26_i группы регистров (i ), блок управления 27, группы элементов И 28 50, элемент И 51, группы элементов ИЛИ 52 60, элементы ИЛИ 61 64; информационный выход 65, первый 66, второй 67, третий 68 и четвертый 69 управляющие выходы.

Блок управления 27 (фиг. 3) содержит первый 70, второй 71, третий 72, четвертый 73 и пятый 74 входы, триггеры 75-80, первую 81_i, вторую 82_i и третью 83_i группы триггеров (i ), элементы И 84 95, элементы ИЛИ 96, 97, элементы ИЛИ-НЕ 98, 99, элементы НЕ 100-102, с первого по семнадцатый выходы 103-119.

В основу работы устройства положено решение задачи наименьших квадратов, которое основано на QR-разложении матрицы: A QR, где Q ортогональная матрица, R , R R₁ верхняя треугольная матрица, Q нулевая матрица.

Задача наименьших квадратов осуществляется решением системы линейных алгебраических уравнений вида АХ В, где A , B , X , N K число уравнений К больше или равно числу неизвестных N, М число правых частей:

(1) или



Требуется найти матрицу Х, минимизирующую AX-B, где норма для любой матрицы S определяется так:

S S.

Если N K, то система уравнений АХ В с N неизвестными для каждой из М правых частей.

Если N K M, а В единичная матрица, то задача (1) сводится к вычислению обратной матрицы А^-1. Матрица Х находится как произведение трех матриц:

Х R₁^-1 Q₁^TB, где Q₁ первые N столбцов матрицы Q.

Матрица Х определяется следующими рекуррентными соотношениями.

Для вычисления матриц R₁ Q₁^T B и W Q₁^T(-В):

a(K i + 1, j, 0) a_ij, 1 i K, 1 j N;

a(K i + 1, N + j, 0) -b_ij, 1 i K, N + 1 j N + M;

K 1, 2, N:

r(k,j,k) a(k,j,k-1), j ; если r(i 1, k, k) 0, то

r(i, k, k) a(i, k, k-1),

S(i, k) 0,

c(i, k) 1; если r(i-1, k, k) 0, то

r(i,k,k) ,

S(i, k) r(i-1, k, k)/r(i,k,k),

c(i,k) a(i, k, k-1)/r(i, k, k),

i (если N=K, то K не берется равным N)

a(i, j, k) c(i, k) r(i-1, j, k) S(i, k) a(i, j, k-1),

r(i, j, k) S(i, k) r(i-1, j, k) + c(i, k) a(i, j, k 1),

i (если N=K, то k N),

j ,

r_kj⁽¹⁾ r(K, j, k), 1 k j N;

_kj= r(K, N+j, k), 1 k N, 1 j M.

Для вычисления матрицы U R₁^-1:

k 1, 2,N:

U_kk 1/r_kk⁽¹⁾;

g(k,j,k) -U_kkr⁽¹_kj⁾, j , k N;

U_ik= g(i,k,k-1)/r⁽¹_kk⁾, i , k 1;

g(i, j, k) g(i, j, k-1) U_ik r_kj^(1),

i , k 1,

j , k N.

Для вычисления матрицы Х -U W:

K 1, 2, N:

x(k,j,k) -U_kkkj, j ;

x(i, j, k) x(i, j, k-1) U_ikkj,

i , k 1,

j ,

x_ij x(i,j,М).

Вычислительный модуль 5 обладает возможностью реализации следующих функций:

A^{j+k+3 j}

B<sup>j+k+3 j

j+k+3</sup>=^j где А^j+k+3, B^j+k+3 и ^j+k+3 значения соответственно на первом, втором и третьем управляющих выходах вычислительного модуля на (j+k+3)-м такте,

E^j+1= где Е^j+1 значение на четвертом управляющем выходе вычислительного модуля на (j+1)-м такте;

^j, ^j, ^j и ^j значения соответственно на первом, втором, третьем и четвертом управляющих входах вычислительного модуля на j-м такте,

F^j+1= где

a^j=

b^j=

c^j=

^j₁= = 1,

^j₂ a^j-1,

^j₃=

^j₄= ^j₁

^j₅ ,

^j₆= ^j₂

^j₇=

^j₈= и

₉^j=₁^j₇^j+₂^j₈^j

₁^j+1=₁^j=(^j, ^j, ^j)= (0, 0, 1),

₂^j+1=₂^j=(^j, ^j, ^j) (0, 1, 0),

₃^j+1=₃^j=(^j, ^j, ^j) (0, 1, 1),

₄^j+1=₄^j=(^j, ^j, ^j) (1, 0, 0),

₅^j+1=₅^j=(^j, ^j, ^j) (1, 0, 1),

^j₁= ,

^j₂= ,

^j₃= ,

^j₄= ^j₁^j₁^j₂^j₃,

₅^j ₂<sup>jj

j</sup>₆= ,

^j₇= ,

₈^j ₃^jj где а^j значение на информационном входе вычислительного модуля на j-м такте;

F^j+1 значение на информационном выходе вычислительного модуля на (j+1)-м такте.

Организация входного и выходного потоков данных задается следующими выражениями.

На вход 1 подаются элементы матриц a_ij и (-b_ij) в моменты времени:

t= -i+j(K+1)-1, i , j ;

t= -i+(j+N)(K+1)-1, i , j .

На вход 3 постоянно подается нулевой сигнал.

На входы 2₁, 2₂, 2₃ подаются значения управляющих сигналов _ij=(, , ) представляющих матрицу вида

_ij= в моменты времени

t= j-1+(i-1)(K+1), i , j .

На выходе 6 формируются элементы х_ij в моменты времени

t= i+(j+N-1)(K+1)+N+K-2, i , j .

Последний элемент Х_NM формируется на ((N+M)(K+1)+2N-3)=М такте.

Рассмотрим работу устройства для решения системы линейных алгебраических уравнений при N 3, M 2 и K 3.

На вход 1 подаются элементы a_ij и (-b_ij), на входы 2₁, 2₂ и 2₃ соответствующие управляющие сигналы , , на вход 3 постоянно подается нулевой сигнал, с выхода 6 снимаются элементы х_ij. В табл. 1, 2 и 3 приведены значения на входах, состояние регистров, значение на выходе узла вычисления обратной величины числа, первом и втором умножителях, сумматора, вычитателе и выходах соответственно вычислительных модулей 5₁, 5₂ и 5₃.