Hjemmeøving 4

Oppgaver fra læreboken

  • 6.1: 1, 16, 31, 40 (scan)
  • 6.2: 3, 13, 23 (scan)

Programmeringsoppgave 1a

Skriv ditt eget Python-program for å løse lineære ligningssystemer ved Gauss-eliminasjon og tilbakesubstitusjon. Det er helt OK å rett og slett implementere algoritmen i tabell 20.1 i Kreyszig. Det er også helt OK å ignorere problemet med singulære matriser; anta altså at ligningssystemet ditt har en unik løsning.

Hint 1: Bruk NumPys todimensjonale arrays for å lagre matrisene. Husk at disse er indeksert fra 0 og (0,0), mens Kreyszigs matriser er indeksert fra 1 og (1,1). Hint 2: Pass på at du lager en dyp kopi når du bytter rader. Kopiér for eksempel elementvis ved hjelp av løkke, eller les mer.

Programmeringsoppgave 1b

Sammenlign svaret til programmet ditt med NumPys løser for lineære ligningssystemer for et valgfritt (ikke-singulært!) ligningssystem. Pass på at du ikke fôrer løseren din med kun heltall da den kan komme til å forsøke å utføre heltallsaritmetikk.

Programmeringsoppgave 2

I denne oppgaven skal ikke noe programmeres på egenhånd. Følgende Python-kode er gitt (du trenger ikke kjøre koden, men kan selvfølgelig gjøre det om du vil):

import numpy as np
 
def foo(a, b, x0, eps):
    n = x0.shape[0]       # Lengden til vektoren x0.
    x = np.zeros(n)
    for j in range(0, n):
        x[j] = x0[j]
 
    done = False
 
    while not done:
        xprev = np.zeros(n)
        for j in range(0, n):
            xprev[j] = x[j]
 
        for j in range(0, n):
            x[j] = b[j]
            for k in range(0, j):
                x[j] = x[j] - a[j, k]*x[k]
            for k in range(j+1, n):
                x[j] = x[j] - a[j, k]*xprev[k]
            x[j] = x[j] / a[j, j]
 
        # Start på konvergenstest.
        i = 0
        for j in range(0, n):
            if abs(x[j] - xprev[j]) > abs(x[i] - xprev[i]):
                i = j
        if abs(x[i] - xprev[i]) < eps*abs(x[i]):
            done = True
        # Slutt på konvergenstest.
 
    return x

Si at vi kjører koden med

a = np.array([[1.0,   -0.25, -0.25, 0    ],
              [-0.25, 1,     0,     -0.25],
              [-0.25, 0,     1,     -0.25],
              [0,     -0.25, -0.25, 1    ]])
b = np.array([[50.0],
              [50.0],
              [25.0],
              [25.0]])
x0 = np.array([[1.0],
               [1.0],
               [1.0],
               [1.0]])
eps = 0.00001
 
foo(a, b, x0, eps)

Hvis vi antar uendelig maskinpresisjon, kan du da være sikker på at koden terminerer (altså at done settes til True på et eller annet tidspunkt)? Hvorfor? Hva nærmer returverdien seg når eps gjøres liten? (Du trenger ikke å finne returverdien, bare forklare hvilken spesiell vektor den er.) Begrunn svarene! (Hint: Begrunnelsen avhenger av den angitte matrisen a).

2012-09-11, spreeman