Finite Element Equations & Poisson Equation

Derivation of Finite Element Equations

• Focuses on the Poisson equation.

Strong Form for the Poisson Equation

• Seeks $u$ satisfying $-\nabla \cdot (c \nabla u) = f$ in $\Omega$.
• Boundary condition: $u = g$ on $\Gamma_D$.
• Neumann boundary condition: $c \nabla u \cdot \mathbf{n} = h$ on $\Gamma_N$.

Weak Form for the Poisson Equation

• Find $u \in V$ where $u = g$ on $\Gamma_D$.
• Integral equation: $\int_\Omega c \nabla u \cdot \nabla v d\Omega = \int_\Omega f v d\Omega + \int_{\Gamma_N} h v dS$ for all $v \in V_0$.
• $V$ is defined as ${v \mid v \in H^1(\Omega) }$.
• $V_0$ is defined as ${v \mid v \in H^1(\Omega), v = 0 \text{ on } \Gamma_D }$.

Finite Element Approximation

• Approximates $u$ as $u_h = \sum_{j=1}^{n} N_j u_j$.
• Approximates $v$ as $v_h = \sum_{i=1}^{n} N_i v_i$.
• Weak form approximation: $\int_\Omega c \nabla u_h \cdot \nabla v_h d\Omega = \int_\Omega f v_h d\Omega + \int_{\Gamma_N} h v_h dS$ for all $v_h \in V_{0h}$.
• Equation becomes: $\int_\Omega c \nabla (\sum_{j=1}^{n} N_j u_j) \cdot \nabla N_i d\Omega = \int_\Omega f N_i d\Omega + \int_{\Gamma_N} h N_i dS$.
• Simplified summation: $\sum_{j=1}^{n} (\int_\Omega c \nabla N_j \cdot \nabla N_i d\Omega) u_j = \int_\Omega f N_i d\Omega + \int_{\Gamma_N} h N_i dS$.

Matrix Form

• Expressed as $\mathbf{K u} = \mathbf{f}$.
• $K_{ij}$ is defined as $\int_\Omega c \nabla N_i \cdot \nabla N_j d\Omega$.
• $f_i$ is defined as $\int_\Omega f N_i d\Omega + \int_{\Gamma_N} h N_i dS$.

Dijkstra's Algorithm

• Used for finding the shortest paths in a graph.

Initialization Steps

• Set the distance $d[v] = \infty$ for each node $v$.
• Set $d[s] = 0$ for the starting node $s$.
• Add all nodes to a priority queue $Q$, prioritized by their distances $d[v]$.

Main Loop

• Loop while $Q$ is not empty.
  • Remove node $u$ with the smallest distance $d[u]$ from $Q$.
  • For each neighbor $v$ of $u$:
    • Calculate the alternative distance $alt = d[u] + w(u, v)$, where $w(u, v)$ is the weight of the edge from $u$ to $v$.
    • If $alt < d[v]$:
      • Update the distance: $d[v] = alt$.
      • Set the predecessor of $v$ to $u$.
      • Update the priority of $v$ in $Q$.

Output

• Returns the shortest distance from the start node $s$ to each node.

Notes

• Works for graphs having non-negative edge weights.
• Uses a Fibonacci heap for the priority queue to achieve a time complexity of $O(E + V \log V)$.

Search Algorithms

Greedy Search

• Expands the node based on heuristic function $h(n)$.
• Not complete; can enter loops.
• Not optimal.
• Time Complexity: $O(b^m)$.
• Space Complexity: $O(b^m)$.

A* Search

• Minimizes $f(n) = g(n) + h(n)$.
• $g(n)$: The cost to reach the node.
• $h(n)$: Estimated cost from node to goal.
• Complete unless there are infinitely many nodes with $f \le f(G)$.
• Optimal.
• Time Complexity: Exponential.
• Space Complexity: Keeps all nodes in memory.

Admissible Heuristics

• $h(n) \le h^*(n)$ for each node $n$.
• $h^*(n)$: Actual cost to reach the goal from $n$.
• Never overestimates the cost to reach the goal.
• Straight-line distance to goal is an example.

Consistent Heuristics

• $h(n) \le c(n, a, n') + h(n')$ for each node $n$ and successor $n'$.
• More restrictive than admissibility.
• If $h(n)$ is consistent, A* using GRAPH-SEARCH is optimal.

Dominance

• $h_2(n) \ge h_1(n)$ for all $n$ (both are admissible).
• $h_2$ dominates $h_1$.
• A* expands fewer nodes with $h_2$.

Heuristics from Relaxation

• Systematic way to invent admissible heuristics.
• Exact solution cost for a relaxed problem is an admissible heuristic for the original.
• Relaxed problem rules result in a directed acyclic graph (DAG).
• Can be generated automatically from problem description.

8-Puzzle Example

• $h_1(n)$: Number of misplaced tiles.
• $h_2(n)$: Sum of distances of tiles to correct positions (Manhattan distance).
• Example State:
  • $h_1(n) = 7$.
  • $h_2(n) = 4 + 0 + 3 + 3 + 1 + 0 + 2 + 4 = 17$.
• Typical search cost values ​​for depth $d=14$:
  • A* with $h_1$: 539 nodes expanded.
  • A* with $h_2$: 113 nodes expanded.
• Typical search cost values ​​for depth $d=24$:
  • A* with $h_1$: 39135 nodes expanded.
  • A* with $h_2$: 1641 nodes expanded.

Machine Learning

Traditional vs. Machine Learning

• Traditional: Data + Program $\rightarrow$ Computer $\rightarrow$ Output.
• Machine Learning: Data + Output $\rightarrow$ Computer $\rightarrow$ Program, learning from data.

Types of Machine Learning

• Supervised Learning
• Unsupervised Learning
• Reinforcement Learning

Supervised Learning

• Learns from labeled data (input + output).
• Learns function that maps input output.

Types of Supervised Learning

• Regression: Predicts continuous value (ex. house price).
• Classification: Predicts discrete value (ex. spam detection).

Unsupervised Learning

• Learns from unlebeled data (input).
• Learns to discover patterns.

Types of Unsupervised Learning

• Clutering: groups similar data points
• Dimensionality Reduction: Reduces number of variables.
• Association Rules Learning: Finds relationships between variables.

Reinforcement Learning

• Learns to make decisions by "trial and error".
• Receives reward/penalty; maximizes reward.
• ex, Robot training / Game playing.

Linear Algebra

Vector Space Definition

• A set $E$ with addition ($E \times E \rightarrow E$) and scalar multiplication ($\mathbb{K} \times E \rightarrow E$) operations.
• $\mathbb{K}$ is a field (e.g., $\mathbb{R}$ or $\mathbb{C}$).

Vector Space Axioms

• Associativity: $(u+v)+w = u+(v+w)$.
• Commutativity: $u+v = v+u$.
• Identity element: $\exists 0 \in E$ such that $u+0 = u$.
• Inverse element: $\exists -u \in E$ such that $u + (-u) = 0$.
• Compatibility: $\lambda(\mu u) = (\lambda \mu)u$.
• Vector addition distributivity: $\lambda(u+v) = \lambda u + \lambda v$.
• Scalar addition distributivity: $(\lambda + \mu)u = \lambda u + \mu u$.
• Scalar multiplication identity: $1u = u$.

Vector Subspace Requirements

• Non-empty.
• Closed under addition: $u, v \in F$ implies $u+v \in F$.
• Closed under scalar multiplication: $u \in F, \lambda \in \mathbb{K}$ implies $\lambda u \in F$.

Linear Combination

• Expression of the form $\lambda_1 v_1 + \lambda_2 v_2 +... + \lambda_n v_n$.

Span

• Set of all possible linear combinations of vectors.

Linear Independence

• Vectors are linearly independent if $\lambda_1 v_1 + \lambda_2 v_2 +... + \lambda_n v_n = 0$ implies $\lambda_1 = \lambda_2 =... = \lambda_n = 0$.

Basis

• Linearly independent set of vectors that spans the vector space.

Dimension

• Number of vectors in a basis of the vector space.

Definition of Linear Transformation

• A function $f: E \rightarrow F$ such that:
  • $f(u+v) = f(u) + f(v)$.
  • $f(\lambda u) = \lambda f(u)$.

Kernel

• The set of vectors in $E$ that map to the zero vector in $F$.

Image

• The set of vectors in $F$ that are the image of at least one vector in $E$.

Rank Theorem

• States: $dim(E) = dim(ker(f)) + dim(im(f))$ for $f: E \rightarrow F$.

Matrices Definition

• A matrix is a table of numbers. An $m \times n$ matrix has $m$ rows and $n$ columns.

Matrix Operations

• Addition is element-wise.
• Scalar multiplication is element-wise.
• Matrix Multiplication: Element $C_{ij} = \sum_{k=1}^{n} A_{ik}B_{kj}$

Transpose

• Obtained exchanging between rows and columns

Inverse

• Matrix $A^{-1}$ such that $AA^{-1} = A^{-1}A = I$.

Determinant

• Scalar indicating matrix properties.

Eigenvalues and Eigenvectors

• A nonzero vector $v$ such that $Av = \lambda v$. Where $\lambda$ = eigenvalue

Research

Categorizing Student Ideas

• Noticing: Ability to direct attention to detail.
• Interpreting: Articulate the significance of observations.
• Deciding: Choosing an appropriate course of action.

Framework for Attending to Student Thinking

Assessing Student Thinking

• Prompts: At what point did you struggle? How did you check your work? Can you show me another way? How is this related to X? What assumptions are you making?

Explanation of Poisson equation strong and weak forms. Includes finite element approximation, seeking solutions satisfying conditions in $\Omega$ with boundary and Neumann conditions. Focuses on integral equation derivation.