代写104A Homework 4调试Python程序

104A Homework 4

July 2024

1 Theory

1.1 Iterative

Consider the iterative scheme

Write the scheme in matrix form. Give the iterative matrix. What happens when ω = 1? (Optional: verify why convergence is guaranteed for 0 < w < 2).

1.2 Norms

a) Show ∥x∥∞ ≤ ∥x∥2 ≤ √ n∥x∥∞ for x ∈ R n.

b) Show that if ∥A∥ < 1 then ∥(I − A) −1∥ ≥ 1+∥A∥/1 for any induced norm.

c) Let ∥A∥2 = p ρ(AT A). Show that ∥A∥2 ≤ p ∥A∥1∥A∥∞.

2 Coding

2.1 Energy Minimization

Consider a graph (V, E) with vertices V = {v0, . . . , vn} ⊂ R 2 and edges E = {(i, j)} connecting the vertices. For example an edge (4, 7) would connect the vertices v4, v7. We fix the position of a subset of the vertices W ⊂ V . Use the built-in Conjugate Gradient, (Python or R), method to minimize the energy

or in other words, find the vertices coordinates to minimize E. Hint: write the norm and solve for x and y coordinates separately. Use the function signature:

miniEner(int n verts,int[][] edges,int[] ind fixVerts, double[][] fixVertsCoords)

return double[][] vertsCoords.

• n verts is |V|, the number of vertices in the graph

• ind fixVerts has the indices of the vertices with fixed positions

• fixVertsCoords is a |W| × 2 matrix with the fixed vertices’ 2D coordinates