Question

In: Computer Science

. Let xj , j = 1, . . . n be n distinct values. Let...

. Let xj , j = 1, . . . n be n distinct values. Let yj be any n values. Let p(x) = c1 + c2x + c3x 2 + · · · + cn x ^n−1 be the unique polynomial that interpolates the data (xj , yj ), j = 1, . . . , n (Vandermonde approach).

(a) Remember that (xj , yj ), j = 1, . . . , n are given. Derive the n × n system Ac = b that determines the coefficients ck (as we did in class for n = 4).

(b) Write a MATLAB script that sets up the Vandermonde matrix V for any given vector x.

(c) Find the condition number (infinity norm) of the matrix V where x consists of n = 10, 20, 30, 40 equally spaced points spanning the interval [0, 1]. Report your results in a table of each n

Solutions

Expert Solution

=== (a) ===

The given "n" points must satisfy the equation of the polynomial as:

This can be re-arranged in the matrix form as:

This can be rearranged in "" form as:

Here:

=== (b) ===

To write the MATLAB script, we require two inputs of "n" and "x". Assuming this, the required script is written as the following:

%=================================================================

format long
clear all;clc;
x = [1 4 -6 7]'; % sample x vector
n = length(x);
V=[];
for i=1:n
V = [V x.^(i-1)];
end
display(V)

% Alternatively, vander command can be used 
V_inbuilt = fliplr(vander(x));
display(V_inbuilt)

%=================================================================

Output image:

===== (c) =====

format long
clear all;clc;

fprintf('Condition number\t n\n');
for n=[10,20,30,40];
    x = linspace(0,1,n); % Equally spaced points
    V = fliplr(vander(x)); %  Vandermonde matrix
    Cond_no = max(sum(V,2)); % Condition number (infinity norm)
    fprintf('\t%d\t\t\t%f\n',n,Cond_no)
end

Output image


Related Solutions

Assume that a sample X = {Xj : 1 ≤ j ≤ 10} of size n...
Assume that a sample X = {Xj : 1 ≤ j ≤ 10} of size n = 10 was drawn from the uniform distribution on the interval (0 < x < 4). Let X[k] denote the k th order statistic based on this sample. 1. Evaluate expected value of X[5] 2. Derive conditional expectation of X[5], given that X[10] = 3.
Given an array A[1..n], with distinct values and k with 1 ≤ k ≤ n. We...
Given an array A[1..n], with distinct values and k with 1 ≤ k ≤ n. We want to return the k smallest element of A[1.....n], in non-decreasing order. For example: A = [5, 4, 6, 2, 10] and k = 4, the algorithm returns [2, 4, 5, 6]. There are at least the following four approaches: a. heapify A and then extract k elements one by one b. sort the array (e.g. using MergeSort or HeapSort) and then read the...
Let n be a positive integer. Let S(n) = n sigma j=1 ((1/3j − 2) −...
Let n be a positive integer. Let S(n) = n sigma j=1 ((1/3j − 2) − (1/3j + 1)). a) Compute the value of S(1), S(2), S(3), and S(4). b) Make a conjecture that gives a closed form (i.e., not a summation) formula for the value of S(n). c) Use induction to prove your conjecture is correct.
Let A[1..n] be an array of distinct positive integers, and let t be a positive integer....
Let A[1..n] be an array of distinct positive integers, and let t be a positive integer. (a) Assuming that A is sorted, show that in O(n) time it can be decided if A contains two distinct elements x and y such that x + y = t. (b) Use part (a) to show that the following problem, re- ferred to as the 3-Sum problem, can be solved in O(n2) time: 3-Sum Given an array A[1..n] of distinct positive integers, and...
Let A[1..n] be an array of distinct positive integers, and let t be a positive integer....
Let A[1..n] be an array of distinct positive integers, and let t be a positive integer. (a) Assuming that A is sorted, show that in O(n) time it can be decided if A contains two distinct elements x and y such that x + y = t. (b) Use part (a) to show that the following problem, re- ferred to as the 3-Sum problem, can be solved in O(n2) time: 3-Sum Given an array A[1..n] of distinct positive integers, and...
Let An = {ai} n i=1 denote a list of n distinct positive integers. The median...
Let An = {ai} n i=1 denote a list of n distinct positive integers. The median mA of An is a value in An such that half the elements in An are less than m (and so, the other half are greater than or equal m). In fact, the median element is said to have a middle rank. (a) Develop an algorithm that uses Sorting to return mA given An. (6%) (b) Now assume that one is given another list...
5. Let n = 60, not a product of distinct prime numbers. Let Bn= the set...
5. Let n = 60, not a product of distinct prime numbers. Let Bn= the set of all positive divisors of n. Define addition and multiplication to be lcm and gcd as well. Now show that Bn cannot consist of a Boolean algebra under those two operators. Hint: Find the 0 and 1 elements first. Now find an element of Bn whose complement cannot be found to satisfy both equalities, no matter how we define the complement operator.
#2 The Jacobsthal sequence is defined by J(1)=J(2)=1 and J(n)=J(n-1)+2J(n-2). Use recursion to write a function...
#2 The Jacobsthal sequence is defined by J(1)=J(2)=1 and J(n)=J(n-1)+2J(n-2). Use recursion to write a function that takes in a positive integer n and returns the nth Jacobsthal number. >>> J(8) 85 >>> J(9) 171 #3 Use recursion to write a function that takes in a positive integer n and returns all n digit numbers containing only odd digits. >>> f(1) [1, 3, 5, 7, 9] >>> f(2) [11, 13, 15, 17, 19, 31, 33, 35, 37, 39, 51, 53,...
7. Let n ∈ N with n > 1 and let P be the set of...
7. Let n ∈ N with n > 1 and let P be the set of polynomials with coefficients in R. (a) We define a relation, T, on P as follows: Let f, g ∈ P. Then we say f T g if f −g = c for some c ∈ R. Show that T is an equivalence relation on P. (b) Let R be the set of equivalence classes of P and let F : R → P be...
Given the likelihood of θ with respect to sample D p(D|θ) = Q j p(xj |θ),...
Given the likelihood of θ with respect to sample D p(D|θ) = Q j p(xj |θ), where D = {x1, · · · , xn} is identically and independently distributed (i.i.d) sample points. Briefly describe how you would find the maximum likelihood estimation and the Bayesian estimation of θ.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT