• https://fsi.informatik.uni-erlangen.de/forum/thread/10559,2-Klausur-23-Juli-2012 Gesamte Klausur

a) O(n²)

b) O(n)

c) O(n)

d) O(n³)

e) O(n)

f) O(n)

g) O(n²)

h) O(n)

a)

    | 3  3  0 |
R = | 0 -1  1 |
    | 0  0  2 |

    | 1  0  0 |
L = | 4  1  0 |
    | 3 -1  1 |

b)

Rx = Q_t*b
x = (-11/3, -1, 0, 0)^T
wobei x_3 und x_4 beliebig wählbar sind

a)

    |  1/3  -2/3  2/3 |
U = | -2/3   1/3  2/3 |
    |  2/3   2/3  1/3 |
	
    | 2  0   0  |
S = | 0  1   0  |
    | 0  0  1/2 |

    | 1  0  0 |
V = | 0  0  1 |
    | 0  1  0 |

b)

Norm: 6

Konditionszahl: 3

Rang-1-Approximation:

| 1 -1 -1 -1|
|-2  2  2  2|
| 0  0  0  0|
|-2  2  2  2|

a)

P1: ρ = 1/3, σ = 0, τ = 2/3
P2: ρ = 0, σ = 1, τ = 0
P3: ρ = 1/3, σ = 1/3, τ = 1/3
P4: ρ = -1, σ = 1, τ = 1

b)

Fläche links unterhalb von R, wenn man eine Gerade zwischen R und S sowie R und T ziehen würde.

c)

α = 1/3, β = 1/2, γ = 1/6

d)

α = 0, 0 ⇐ β ⇐ 1, 0 ⇐ γ ⇐ 1

d)

f_M = 1

d)

…

a)

c_0 = (8, 8)^T
c_1 = (4, 8)^T
c_2 = (4, 6)^T
c_3 = (6, 5)^T
d_0 = (6, 5)^T
d_1 = (8, 4)^T
d_2 = (12, 4)^T
d_3 = (16, 8)^T

b)

…

c)

…

d)

…

a)

float CoonsPatch::evaluateAt(float s, float t) {
	float f_t = (1-s) * m_t0.f(t) + s * m_t1.f(t);
	float f_s = (1-t) * m_s0.f(s) + t * m_s1.f(s);
	float f_st = (1-t) * (1-s) * m_t0.f(0) + (1-s) * t * m_s1.f(0) +
				(1-t) * s * m_t1.f(0) + t * s * m_t1.f(1);
 
	return f_s + f_t - f_st;
}

b)

float CoonsPatch::evaluateDerivativeS(float s, float t) {
	float f_t = (-1) * m_t0.f(t) + 1* m_t1.f(t);
	float f_s = (1-t) * m_s0.d(s) + t * m_s1.d(s);
	float f_st = (1-t) * (-1) * m_t0.f(0) + (-1) * t * m_s1.f(0) +
				(1-t) * m_t1.f(0) + t * m_t1.f(1);
 
	return f_s + f_t - f_st;
}

a)

double optimizer::optimize(double x0, double y0, const unsigned int maxIter) const {
	double x = x0;
	double y = y0;
 
	for(int k = 0; k < maxIter; k++) {
		double sx, sy;
 
		searchDirection(x, y, sx, sy);
 
		double t = lineSearch(x, y, sx, sy);
 
		x = x + t * sx;
		y = y + t * sy;
 
		if(Math.sqrt(sx * sx + sy * sy) < m_gradientEpsilon)
			break;
	}
 
	return m_targetFunction.f(x, y);
}

b)

double optimize::lineSearch(const double x, const double y, const double dx, const double dy) const {
	double line, fct;
	double t = m_tMax;
 
	do {
		double gx, gy;
		m_targetFunction.gradf(x, y, gx, gy);
 
		double tmp = dx * gx + dy * gy;		
		line = m_targetFunction.f(x, y) + t * m_c1 * tmp;
 
		fct = m_targetFunction.f(x + t * dx, y + t * dy);
 
		t = t * m_reductionFactor;
	} while(line > fct);
 
	return t;
}

c)

void gradient_ascent_optimizer::searchDirection(double x, const double y, double& dx, double& dy) const {
	m_targetFunction.gradf(x, y, dx, dy);
 
	dx = -dx;
	dy = -dy;
}

d)

void newton_optimizer::searchDirection(const double x, const double y, double& dx, double& dy) const {
	double h11, h12, h21, h22, gx, gy;
	m_targetFunction.inverseHessian(x, y, h11, h12, h21, h22);
	m_targetFunction.gradf(x, y, gx, gy);
 
	dx = h11 * gx + h12 * gy;
	dy = h21 * gx + h22 * gy;
 
	if(dx < 0 || dy < 0) {
		dx *= -1;
		dy *= -1;
	}
}

a)

…

b)

…

c)

F1: nicht separierbar
F2: separierbar mit (1, 2, 3)^T und (-1, 0, 1)
F3: nicht separierbar

a)

(1, -1/2, 0, 2)^T

b)

(1, -1/2, 3/2, 2)^T

c)

B: Starkes Spaltensummenkriterium
→ Jacobi-Verfahren konvergiert für B

C: ist unzerlegbar
schwaches Zeilen- und Spaltensummenkriterium
mindestens für eine Zeile/Spalte gilt, dass der Wert auf der Diagonalen größer als die restlichen Einträge in der Zeile/Spalte ist (im Betrag)
→ Jacobi-Verfahren konvergiert für B

a)

x_2 = 1, x_3 = 2

b)

x_1 = 3, x_3 = 2,75

c)

x_1+1 = (3/16, 1/4)^T

d)

Frage 1: \
Nein, das Newton-Verfahren ist nur lokal konvergent

Frage 2: \
Nein, das Sekanten-Verfahren ist nur lokal konvergent

Frage 3: \
p = 2 für einfache Nullstellen
p = 1 für mehrfache Nullstellen