Jakie części algebry liniowej są używane w informatyce?

Czytam Algebrę liniową i jej aplikacje, aby pomóc w zrozumieniu materiałów informatycznych (głównie uczenia maszynowego), ale martwię się, że wiele informacji nie jest użytecznych dla CS. Na przykład wiedza o tym, jak skutecznie rozwiązywać układy równań liniowych, nie wydaje się bardzo przydatna, chyba że próbujesz zaprogramować nowy układ równań. Dodatkowo, książka dużo mówiła o rozpiętości, liniowej zależności i niezależności, kiedy macierz ma odwrotność, i relacjach między nimi, ale nie mogę wymyślić żadnego zastosowania tego w CS. Jakie części algebry liniowej są używane w CS?

Wspomniane części są podstawowymi pojęciami algebry liniowej. Nie można zrozumieć bardziej zaawansowanych pojęć (na przykład wartości własnych i wektorów własnych) przed pierwszym zrozumieniem podstawowych pojęć. W matematyce nie ma skrótów. Bez intuicyjnego zrozumienia pojęć zakresu i niezależności liniowej nie zajdziesz daleko w algebrze liniowej.

Niektóre algorytmy działają tylko z macierzami pełnej rangi - czy wiesz, co to oznacza? Czy wiesz, co może sprawić, że matryca nie będzie pełna? Jak sobie z tym poradzić? Nie będziesz miał pojęcia, jeśli nie wiesz, czym jest liniowa niezależność.

Algorytm eliminacji Gaussa, który jest używany do rozwiązywania równań liniowych, może być niestabilny numerycznie, jeśli zostanie nieprawidłowo zaimplementowany, i w niektórych przypadkach możesz się martwić. Bez zrozumienia algorytmu nie wiadomo, skąd pochodzi problem i czy można coś z tym zrobić - nie na poziomie algorytmów rozwiązywania równań liniowych, ale na poziomie wymyślania poprawnych równań liniowych do rozwiązania.

Krótko mówiąc, nie bądź leniwy i wierz, że te rzeczy są przydatne.

Algebra liniowa jest czasem niezwykle przydatna i wydajna w algorytmach graficznych. Za pomocą twierdzenia o macierzy-drzewie możesz skutecznie policzyć liczbę drzew rozpinających na wykresie (musisz zrozumieć wartości własne). Bardziej wymagającym zastosowaniem, w którym potrzebujesz jeszcze mocniejszego zrozumienia algebry liniowej, jest algorytm FKT do obliczania liczby idealnych dopasowań na wykresie planarnym w czasie wielomianowym.

Istnieje wiele innych ekscytujących przykładów zastosowań algebry liniowej w teorii grafów algebraicznych i teorii grafów spektralnych . Algorytmy, które powstają, służą nie tylko do liczenia problemów, jak dwa przykłady, które podałem. Możesz na przykład sprawdzić łączność lub obliczyć średnicę wykresu .

Jednym z najbardziej znanych zastosowań algebry liniowej jest algorytm Google Pagerank :

Wartości PageRank są wpisami dominującego lewego wektora własnego zmodyfikowanej macierzy przylegania.

Niemal wszystko, co obejmuje grafikę komputerową, animację, wizję komputerową, przetwarzanie obrazu, obliczenia naukowe lub symulację zjawisk fizycznych, będzie wymagało szerokiego zastosowania wektorów i matryc (algebry liniowej) od prostych rzeczy, takich jak reprezentacja przekształceń przestrzennych i orientacji, po bardzo złożone algorytmy. Te rzeczy były kiedyś domeną superkomputerów, ale teraz te same pola są rdzeniem wszystkich najfajniejszych aplikacji na komputerze, telefonach i wszędzie indziej, od gier wideo przez fotografię komputerową po samochody samobieżne. Algebra liniowa jest wszędzie.

Istnieje wiele algorytmów i technik opartych na algebrze macierzowej. I to świetnie. Analiza głównego składnika jest przykładem dość użytej stosowanej algebry liniowej. To samo można powiedzieć o analizie Fouriera, która ma również swoje korzenie w ortogonalności i produktach wewnętrznych. Istnieją więc bezpośrednie aplikacje.

ALE , co jeszcze ważniejsze, uczenie się algebry liniowej jest cenne, ponieważ uczy, jak myśleć w określony sposób. Większość dobrych klas algebry liniowej kładzie nacisk na uogólnienie, logikę i dowody. Czy coś jest prawdą ogólnie, czy tylko w niektórych konkretnych, powszechnych przypadkach? Jak możesz być pewien? Możliwość pomyślenia, jak udowodnić swoje założenia, jest dobra, ponieważ pomaga powstrzymać się od robienia złych założeń i pisania kodu, który nie jest generalny w sposób, w jaki zakładasz. Pomaga również zastanowić się, jak uogólnić rzeczy, które w innym przypadku mogłyby być trudne do uogólnienia, i które pozwalają rozwiązać większe problemy.

Podsumowując, należy pamiętać, że algebra liniowa jest dobra, ponieważ podnosi ciężar części mózgu, która jest przydatna w informatyce.

Rozwiązywanie układu równań liniowych (które można wykonać metodą eliminacji Gaussa), programowanie liniowe (które można rozwiązać metodą simpleks), najmniejszych kwadratów i detekcja skompresowana (patrz artykuł z Wikipedii) to praktyczne problemy, które pojawiają się w wielu obszary zastosowania. Algebra liniowa pomaga w opracowaniu poprawnych i wydajnych algorytmów dla tych problemów.

Zobacz tekst [Cormen, Leiserson, Rivest i Stein, „Wprowadzenie do algorytmów, wydanie trzecie”], w którym rozdział 28 dotyczy operacji na macierzach, a rozdział 29 dotyczy programowania liniowego.