• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Приклади створення розріджених масивів

Схема IV

Схема III

Схема II

Інформація про дану матрицю зберігається в трьох масивах: VE - значення ненульових елементів, RI - індексів рядків і CIP - покажчиків індексів стовпчиків. Елемент RI(α) містить індекс рядка α-ого елементу VE - VE(α). Якщо перший ненульовий елемент β-ого стовпчика даної матриці розміщується в VE(t_β), тоді t_β зберігається в β-ому елементі CIP, т.ч. CIP(β) = t_β. Очевидно, VE та RI складаються з τ елементів, а CIP з n елементів. Отже ця схема вимагає загальне число в 2τ + n комірок.

Матриця A₅ зберігатиметься таким чином:

VE = (a₂₁, a₄₁, a₅₂, a₁₃, a₃₃, a₂₄, a₄₅)

RI = (2, 4, 5, 1, 3, 2, 4)

CIP = (1, 3, 4, 6, 7)

Вищевикладеною схемою легко користуватися. Наприклад, a₃₃ може бути знайдене таким чином. Оскільки CIP(3) = 4, тоді RI(4) дасть індекс рядка першого ненульового елементу третього стовпчика. Якщо a₃₃ ≠ 0, тоді RI(4) або один з наступних за ним елементів RI передуючих першому ненульовому елементу четвертого стовпчика, повинен бути рівний 3. У нашому випадку RI(5) = 3, т.я. VE(5) містить a₃₃.

Кожному ненульовому елементу даної матриці однозначно ставиться у відповідність ціле число λ(i, j) вигляду:

λ(i, j) = i + (j – 1)n, a_ij ≠ 0

Зберігання ненульових елементів забезпечується двома масивами: VE - значень ненульових елементів і LD, в кожному з яких міститься τ елементів. В LD(α) знаходиться λ(i, j), відповідне a_ij з VE(α), де α = 1,2, …, τ.

Матриця A₅ зберігається у вигляді:

VE = (a₂₁, a₄₁, a₅₂, a₁₃, a₃₃, a₂₄, a₄₅)

LD = (2, 4, 10, 11, 13, 17, 24)

Елементи зберігаються по стовпчиках.

PVE - елементи;

PLD - приведений індекс елементу в суцільному уявленні по стовпчиках.

Початкова матриця може бути відновлена по цій схемі зберігання таким чином. Відповідно до даним вище визначенням для λ(i, j) є очевидним, що j є найменше ціле, більше або рівніше λ(i, j)/n та i = λ(i, j) – (j -1)n.

Наприклад, якщо λ(i, j) = LD(5) = 13, тоді λ(i, j)/n =13/5 і найменше ціле число більше або рівніше λ(i, j)/n буде 3 та i = λ(i, j) – (j -1)n = 13 – 10 = 3.

Якщо A - симетрична матриця, в якій для всіх i ≥ j a_ij = 0, i – j > θ_i, де θ_i набагато менше n і в загальному випадку може мати різні значення для кожного i, то така матриця називається симетричною стрічковою матрицею з шириною стрічки, що локально змінюється.

У такій матриці можна запам'ятовувати тільки елементи на головній діагоналі і нижче. Зберігається матриця у вигляді двох масивів:

VE - значення ненульових елементів і ;

PD - положення діагональних елементів в масиві VE.

Для кожного рядка в VE зберігаються крайній лівий ненульовий елемент і всі наступні елементи, розташовані праворуч від нього аж до діагонального включно. Тому i-й рядок матриці A вимагає θ_i + 1 комірок для зберігання і VE складатиметься з n

∑ θ_i + 2n комірок для зберігання матриці A.

i=1

Наприклад, хай у нас є матриця

Тоді її можна представити у вигляді:

1 2 3 4 5 6 7 8 9 10 11 12

VE = (a₁₁, a₂₁, a₂₂, a₃₂, a₃₃, a₄₂, 0, a₄₄, a₅₂, a₅₃, 0, a₅₅)

PD = (1, 3, 5, 8, 12)

Елемент a_ij початкової матриці може бути відновлений таким чином. Положення a_ij у VE визначається значенням PD(i) – (i – j), якщо тільки PD(i) – (i – j) > PD(i – 1). Остання умова означає, що a_ij не лежатиме ліворуч від першого ненульового елементу i-ого рядка, інакше a_ij = 0 і не зберігається в VE.

Наприклад, щоб знайти елемент a₅₃ у масиві VE, обчислюємо PD(5) – (5 – 3) = 12 – 2 = 10 > 8 = PD(4) і, отже, a₅₃ зберігається в VE(10).

Головна перевага цієї схеми:. Якщо в процесі обчисленя, наприклад, при виключеннях по методу Гауса, створюються додаткові ненульові елементи тільки вправо від крайнього лівого елементу кожного рядка, то вони можуть запам'ятовуватися в VE без переміщень всіх наступний за ними елементів.

Діагональна блочна форма (BDF)

Матриця A визначена формулою:

Має форму BDF, якщо для всіх i ≠ j підматриці A_ij = 0 и всі діагональні підматриці A_ij є квадратними матрицями.

Трикутна блочна форма (BTF)

Матриця A задана у вигляді:

причому підматриці A_ij = 0 для i ≠ p та підматриці A_ii, i = 1, 2, …, p є квадратними матрицями, то говорять, що матриця A має трикутну блокову форму BTF.

Трикутна стрічкова форма (BNTF)

Говорять, що матриця B має трикутну стрічкову форму, якщо існує таке β 0 ≤ β ≤ n, де b_ij = 0 для всіх i – j > β, та значення β не може бути зменшено перестановками рядків і стовпчиків матриці B.

Хай перший ненульовий елемент i-ой рядка матриці B знаходиться в q_i-ому стовбці. Тоді визначаємо:

β _i = i- q_i, q_i ≤ i

β _i = 0, q_i > i

Очевидно, що якщо матриця B має форму BNTF, то max β _i = β .

Відмітимо, що трикутна блочна форма (BTF), описана в попередньому розділі, є спеціальним випадком BNTF (β + 1 є в цьому випадку розміром найбільшого діагонального блоку матриці B).

Стрічкова форма (BF)

Визначення. Матриця A, у якої a_ij = 0 при |i – j| > β, називається стрічковою матрицею. Якщо до того ж a_ij ≠ 0 для всіх |i – j| ≤ β, то вона називається повною стрічковою матрицею. Величина 2β + 1 називається шириною стрічки.

Гіперматрична схема

Дамо визначення гіперматриці.

Гіперматрицею k-го порядку називається така матриця, елементами якої є гіперматриці k-1-го порядку. Гіперматрицею першого порядку є така матриця, елементами якої є скаляри. Гіперматриця k-го порядку може бути предствлена в вигляді гіперматриці k+1-го порядку шляхом групування її сусідніх елементів.

Оскільки матриця з одним елементом з точки зору алгебри залишається матрицею, процес групування та підвищення порядку може продовжуватися нескінченно. Наведемо приклад

Схема зберігання підматриць або гіперматриці в цьому випадку може бути будь-якою.

Розглянемо процес створення двовимірних розріджених масивів на конкретному навчальному прикладі, який, для розуміння цього механізму, має невелику кількість рядків і стовпців. Хоча такі приклади не завжди відповідатимуть реальним інженерним розрахункам, проте у нашому випадку розроблена програма здатна працювати з надзвичайно великими масивами.

Отож, основне завдання топологічного опису будь-якої електронної схеми (рис. 3, а) полягає в тому, щоби перевести графічну інформацію про з'єднання її компонент у формальні математичні позначення, які потім використовуються для написання алгебричних рівнянь та нерівностей .

Основою топологічного опису є граф, який складається з гілок – сукупності відрізків довільної довжини і форми, а також вершин – точок перетину вершин. Важливим поняттям теорії графів є дерево графу (рис. 3, б), яке складається з сукупності гілок електронної схеми, охоплює усі її вузли, але не містить жодного контура. Графічне подання зв'язків у електронній схемі переводиться у формальні математичні позначення за допомогою топологічних матриць (рис. 3, в).

Читайте також:

1. ACCESS. СТВОРЕННЯ ЗВІТІВ
2. ACCESS. СТВОРЕННЯ ФОРМ
3. А. Створення власної папки.
4. Автоматичне і ручне створення об’єктів.
5. Адаптація законодавства України до законодавства ЄС - один із важливих інструментів створення в Україні нової правової системи та громадянського суспільства
6. Адаптація законодавства України до законодавства ЄС - один із важливих інструментів створення в Україні нової правової системи та громадянського суспільства
7. АЛГОРИТМ СТВОРЕННЯ БРЕНДУ
8. Алгоритм створення тренінгової програми
9. Безкласова адресація та створення підмереж.
10. Болонська конвенція як засіб створення зони європейської вищої освіти.
11. В чому полягає явище тунелювання через потенціальний бар’єр, наведіть приклади.
12. Визначення і приклади

Переглядів: 1161